Es ist nicht sicher, ob sich die antike Siedlung von Sitia genau an der Stelle der heutigen Stadt befand. In der Umgebung wurden jedoch mittel- und spätminoische Gräber, geometrische und spätere Figuren und Keramik, römische Gebäude sowie eine frühchristliche Basilika entdeckt. Die Existenz einer Siedlung während der ersten byzantinischen, arabischen, zweiten byzantinischen und venezianischen Zeit gilt hingegen als gesichert.

Die byzantinische Siedlung war von Wehrmauern umgeben und bildete eine befestigte Stadt. Venezianische Karten zeigen diese Befestigungen, von denen im Laufe der Zeit einzelne Abschnitte entdeckt wurden. Der Mauerring hatte annähernd die Form eines Dreiecks, dessen Grundseite zum Meer ausgerichtet war. Er begann bei den römischen Fischbecken in der Nähe des heutigen Zollgebäudes und führte bergauf zur Kazarma, wo die beiden Seiten der Befestigung zusammentrafen.

Der Name Kazarma leitet sich vom venezianischen Ausdruck Casa di Arma ab. Das Gebäude diente als Kaserne der Garnison und als Verwaltungszentrum des mittelalterlichen Sitia. Es war nicht die gesamte Burg, sondern eines der bedeutendsten Gebäude innerhalb der befestigten Stadt. Zu Beginn des 13. Jahrhunderts ließ der Genueser Enrico Pescatore die Befestigungen instand setzen oder verstärken. Später führten auch die Venezianer mehrfach umfangreiche Arbeiten durch.

Nach dem verheerenden Erdbeben von 1508 wurden die Mauern repariert. Beim Angriff von Hayreddin Barbarossa im Jahr 1538 erlitten sie jedoch erneut schwere Schäden. Die venezianischen Amtsträger Paravizzini und Savorgnan schlugen ihren Abriss vor, doch die Einwohner brachten 1.500 Dukaten für die Instandsetzung des Verteidigungssystems auf. Auch ein späterer Vorschlag zum Abriss wurde durch den Widerstand der venezianischen Statthalter Bembo und Gongara verhindert.

Im Jahr 1626 galt Sitia praktisch als unbefestigt. Der Militäringenieur Francesco Basilicata stellte 1630 in einem Bericht fest, dass die Lage der Stadt nur schwer wirksam zu verteidigen sei. Da eine Verlegung der gesamten Siedlung unmöglich war, sollte sie dennoch geschützt werden. Ingenieure und finanzielle Mittel wurden nach Sitia geschickt, und Teile der alten Mauern wurden abgetragen, um sie durch stärkere Befestigungen zu ersetzen.

Die Arbeiten konnten vor dem osmanischen Vormarsch auf Kreta nicht abgeschlossen werden. Die Einwohner wurden evakuiert und viele von ihnen nach Candia, dem heutigen Heraklion, gebracht. Eine kleine Garnison blieb bis 1651 in Sitia. Danach gaben die Venezianer die Stadt endgültig auf und zerstörten einen großen Teil ihrer Befestigungen.

Die Stadtmauern wurden nie wieder aufgebaut, und Sitia blieb mehr als zwei Jahrhunderte weitgehend verlassen. Die moderne Stadt wurde 1869 nach dem Stadtplan von Avni Pascha gegründet und offiziell Avnie genannt. Unter den griechischen Einwohnern setzte sich diese Bezeichnung jedoch nicht durch. Heute sind die Mauern nicht mehr sichtbar, und die Kazarma ist das bedeutendste erhaltene Denkmal der befestigten mittelalterlichen Stadt.