Η Σητεία, ως οικισμός, κατά την αρχαιότητα δεν είναι βέβαιο ότι βρισκόταν στην θέση που είναι σήμερα, αν και έχουν βρεθεί μεσομινωικοί και υστερομινωικοί τάφοι, γεωμετρικά και Ελληνικά ειδώλια, όστρακα, ρωμαϊκά κτίρια και μια Παλαιοχριστιανική Βασιλική. Βέβαιο είναι όμως ότι υπήρχε κατά την Πρωτοβυζαντινή, την Αραβική, τη Β Βυζαντινή και την Ενετική Περίοδο. Ο Βυζαντινός οικισμός της Σητείας περιβαλλόταν από τείχη, ήταν δηλαδή κάστρο. Έχουν βρεθεί ενετικοί χάρτες που αποτυπώνουν τα Βυζαντινά τείχη, τμήματα των οποίων έχουν εντοπιστεί κατά καιρούς. Τα τείχη αυτά, σχηματίζοντας ένα ισοσκελές τρίγωνο, τη βάση του οποίου αποτελούσε η παραθαλάσσια πλευρά του, άρχιζαν λίγο πιο πέρα από το τελωνείο της πόλης, όπου βρίσκονταν οι ρωμαϊκές ιχθυοδεξαμενές, κι έφταναν ως την Καζάρμα, όπου σχηματιζόταν η γωνία του τριγωνικού περίβολου, με τον ανατολικό βραχίονά τους.
Τα τείχη και το φρούριο επισκεύασε το 1204, μετά την κατάληψη της πόλης, ο Γενουάτης αρχιπειρατής Ερρίκος Πεσκατόρε. Επισκευές όμως έγιναν κι από τους Ενετούς σε διάφορα χρονικά διαστήματα. Μια τέτοια επισκευή ήταν που έγινε το 1508 μετά από καταστροφικό σεισμό. Κατά την επιδρομή του Χαϊρεντίν Μπαρμπαρόσα το 1538, τα τείχη του κάστρου υπέστησαν τεράστιες καταστροφές και οι Ενετοί κυβερνήτες Παραβιτσίνι και Σαβοργκάν ζήτησαν την κατεδάφισή τους. Για να μην γίνει αυτό, οι κάτοικοι αναγκάστηκαν να συμβάλουν οικονομικά με 1500 δουκάτα για την επιδιόρθωση όλου του οχυρωματικού συστήματος της πόλης. Αλλά η πλευρά του τείχους προς τη θάλασσα αργότερα, λόγω των μεγάλων ζημιών που είχε υποστεί, δεν μπορούσε να επιδιορθωθεί και ζητήθηκε και πάλι η κατεδάφιση του κάστρου. Η αντίδραση όμως των Βάιλων της Σητείας Bemb και Gongara απέτρεψε πάλι αυτό το ενδεχόμενο.
Το 1626, λίγα χρόνια πριν από τον Κρητικό Πόλεμο, η πόλη θεωρήθηκε «ανοχύρωτη». Το 1630 σε έκθεση που υπέβαλε ο στρατιωτικός αρχιτέκτονας Fr. Basilicata, προς τον υπεύθυνο για την άμυνα του νησιού γενικό καπιτάνο Pietro Giustiniano ανέφερε ότι η θέση της πόλης είναι ακατάλληλη για οχύρωση και ασφάλεια, αλλά πρέπει να προφυλαχτεί, καθώς η μεταφορά της ήταν αδύνατη. Στάλθηκαν τότε μηχανικοί και χρήματα για την επισκευή των τειχών και του φρουρίου, οι οποίοι κατεδάφισαν τα τείχη για να ξανακτίσουν ισχυρότερα. Ωστόσο, δεν πρόλαβαν καθώς εμφανίστηκαν στην Κρήτη οι Οθωμανοί. Οι κάτοικοι απομακρύνθηκαν από την πόλη και μεταφέρθηκαν στο «Μεγάλο Κάστρο», το σημερινό Ηράκλειο, και η μικρή φρουρά που έμεινε, άντεξε μέχρι το 1651.
Τα τείχη της Σητείας δεν ξανακτίσθηκαν ποτέ και η πόλη έκτοτε έπαψε να υπάρχει για δύο ολόκληρους αιώνες, μέχρι το 1869 που ξανασυνοικίσθηκε με σχέδια του Αυνή Πασά, που γι’αυτό το λόγο οι Τούρκοι την ονόμασαν «Αυνιέ», ονομασία που ποτέ δεν επικράτησε. Σήμερα τα τείχη δεν είναι ορατά και μόνο το φρούριο της Καζάρμα έχει μείνει για να θυμίζει ότι η Σητεία ήταν κάποτε ένα από τα κάστρα της Κρήτης.
