Η Σητεία κατοικείται από τη νεολιθική εποχή. Επίσης, έχουν βρεθεί ανακτορικά μινωικά κτίρια και τείχη στη θέση Πετράς. Η πόλη θεωρείται ότι είναι κτισμένη στην τοποθεσία της Αρχαίας Ητείας ή Σηταίας, που ήταν η πατρίδα του Μύσωνα.
Ο Μύσων έχει αναφερθεί ως ένας από τους επτά σοφούς της αρχαιότητας, αντικαθιστώντας τον Περίανδρο. Κατά την ελληνική μυθολογία, ο Ηρακλής συγκέντρωσε από αυτήν την πόλη (όπως και από ολόκληρη την Κρήτη) πολεμιστές κατά των Λαιστρυγόνων και, νικώντας τους στην κεντρική Ιταλία, ίδρυσε τη νέα Σητεία, λίγο πιο έξω από τη Ρώμη.
Επίσης, η αρχαία Ετιά (άλλο όνομα της Σητείας) ήταν λιμάνι της Πραισού, της μεγαλύτερης αντιπάλου της Ιεράπυτνας. Κατά τη Βυζαντινή Περίοδο η πόλη άκμασε ως εμπορικό λιμάνι. Η Μεσαιωνική πόλη προστατευόταν από μεγάλο τοίχος κι από το φρούριο Καζάρμα, που βρίσκεται κοντά στο λιμάνι.
Όταν οι Ενετοί κατέλαβαν την Κρήτη, έδωσαν πολύ μεγάλη σημασία στην περιοχή και προσπάθησαν να την οχυρώσουν. Για να σταθεροποιήσουν την κυριαρχία τους, οι Βενετοί έκτισαν σε διάφορα σημεία στρατηγικής σημασίας της επαρχίας πολλά φρούρια που σώζονται και σήμερα (π.χ Καζάρμα).Η Σητεία γνώρισε μεγάλη άνθηση σε όλους τους τομείς και έγινε η σημαντικότερη πόλη της Ανατολικής Κρήτης. Τότε μεγαλούργησε ένας από τους μεγαλύτερους εκπροσώπους της Ελληνικής Λογοτεχνίας, ο Βιτσέντζος Κορνάρος (1553-1613), με τα περίφημα του ποιήματα «Ερωτόκριτος» και «Η θυσία του Αβραάμ». Ο μεγάλος σεισμός του 1508 και οι επιδρομές του πειρατή Μπαρμπαρόσα το 1538 κατέστρεψαν μεγάλο μέρος της, ενώ το 1651 οι Ενετοί κατέστρεψαν εντελώς την οχύρωση της, πριν την παραδώσουν στους Τούρκους. Κατά τη διάρκεια της Τουρκοκρατίας, η πόλη και το κάστρο του Καζάρμα ξαναχτίστηκε και της δόθηκε το τουρκικό όνομα Αβνιέ, το οποίο όμως δεν επικράτησε.