Το κάστρο της Μυτιλήνης καταλαμβάνει το υψηλότερο σημείο της χερσονήσου στο βορειοανατολικό άκρο της πόλης. Στην αρχαιότητα και μέχρι τους πρώτους βυζαντινούς χρόνους η σημερινή χερσόνησος ήταν νησί, που χωριζόταν από την υπόλοιπη Λέσβο με τον λεγόμενο «Εύριπο των Μυτιληναίων?, το κανάλι που διατρέχοντας περίπου το δρόμο της σημερινής αγοράς ένωνε τα δύο λιμάνια της πόλης.

Το βυζαντινό κάστρο έχει καταλάβει τη θέση της αρχαίας ακρόπολης, η μορφή της οποίας μας είναι άγνωστη κατά την περίοδο της κλασσικής, ελληνιστικής και ρωμαϊκής αρχαιότητας.

Η παλαιότερη φάση κατασκευής του κάστρου ανάγεται στον 6ο αιώνα και στην ευρεία οικοδομική δραστηριότητα του αυτοκράτορα Ιουστινιανού, ωστόσο τα λιγοστά ιστορικά και ανασκαφικά στοιχεία δεν μας επιτρέπουν την εξαγωγή ασφαλών συμπερασμάτων.

Η πρώτη μνεία για την ύπαρξη του κάστρου προέρχεται από μια πατριαρχική συνοδική απόφαση του 1324, η οποία αναφέρει ένα μετόχι της μονής των Οσίων Πατέρων Δαφνέας μέσα στο Κάστρο της Μυτιλήνης.

Από τη βυζαντινή φάση σώζονται σήμερα μόνο τρία τμήματα: μία βυζαντινή πυλίδα στη βόρεια πλευρά των τειχών, ο ανατολικός τοίχος του κεντρικού οχυρωματικού περιβόλου και η δεξαμενή στο μεσαίο κάστρο.

Στα 1355 η Λέσβος παραχωρείται ως προίκα στην αδελφή του αυτοκράτορα Ιωάννη Ε΄ Παλαιολόγου, κατά τον γάμο της με τον Francisco Gattelusio. Η ηγεμονία του οίκου των Gattelusi θα διαρκέσει μέχρι το 1462.

Από τα πρώτα έργα που πραγματοποιούν οι νέοι ηγεμόνες είναι η ανακαίνιση του κάστρου, το 1373, όπως μας πληροφορεί η λατινική επιγραφή που είναι εντοιχισμένη πάνω από τη Μεσαία (Δυτική) πύλη. Η νέα οχύρωση ακολουθεί σε γενικές γραμμές την προϋπάρχουσα βυζαντινή. Ο χώρος διαρθρώνεται σε δύο τμήματα, το σημερινό Πάνω και το Μεσαίο Κάστρο, ενώ ο ντόπιος πληθυσμός κατοικεί στο οχυρωμένο προάστιο του Μελανουδίου.

Ο δυνατός σεισμός του 1384 υπήρξε καταστροφικός για την πόλη και το κάστρο. Από τη βασιλική οικογένεια επιβίωσε μόνο ο μικρότερος γιος Giacomo.

Μέχρι και το 1403 δεν φαίνεται να αποκαταστάθηκαν οι ζημιές που προκάλεσε ο σεισμός. Οι δύο τελευταίοι Γατελούζοι, ο Δομένικος (1445-1458) και ο αδερφός του Νικόλαος (1458-1462) πραγματοποίησαν εργασίες ενίσχυσής του. Επί Δομένικου τοποθετήθηκαν τα πρώτα κανόνια ενώ επί Νικολάου διαμορφώθηκαν προμαχώνες και ενισχυτικά τείχη, πολεμίστρες, τάφροι και παρατηρητήρια. Από την γενουατική φάση του κάστρου σώζονται σήμερα ο κεντρικός οχυρωματικός περίβολος (Donjon) και τα ερείπια της εκκλησίας του Αγ. Ιωάννη.

Το Σεπτέμβριο του 1462 οι Οθωμανοί κατέλαβαν την πόλη της Μυτιλήνης, ύστερα από μία σύντομη αλλά βίαιη πολιορκία.

Το 1501, επί Σουλτάνου Bayezid και μετά τις καταστροφές που υπέστη το Κάστρο κατά τη διάρκεια του Ενετοτουρκικού Πολέμου (1499-1504), επισκευάστηκαν οι κατεστραμμένες οχυρώσεις του βόρειου λιμανιού, κατασκευάστηκαν δύο μεγάλοι στρογγυλοί οχυρωματικοί πύργοι με κανονιοθυρίδες και αναπτύχθηκαν νέα τείχη.

Νέες κατασκευές εκσυγχρονισμού του κάστρου αναλήφθηκαν το 1643/44 από τον Μπεκήρ πασά, επί των ημερών του σουλτάνου Ιμπραήμ Χαν, ίσως εν όψει του Κρητικού πολέμου είτε εξαιτίας καταστροφής από σεισμό. Πραγματοποιήθηκαν επισκευές των τειχών και ανέγερση ενός νέου τείχους μπροστά από το υφιστάμενο μεσαιωνικό. Μπροστά από τις νέες αυτές κατασκευές δημιουργήθηκε μια βαθιά και πλατιά τάφρος.

Το 1756 ο ναύαρχος Κουραματζής πρόσθεσε ένα πολυγωνικό πύργο κοντά στο λιμάνι της Επάνω Σκάλας.

Νέες εκτεταμένες επισκευαστικές εργασίες πραγματοποιήθηκαν, ύστερα από σεισμό, στα 1765/66.

Στη διάρκεια του 19ου αιώνα η λειτουργία και ο χαρακτήρας του κάστρου είχαν πλέον μεταβληθεί. Το κάστρο προσέλαβε περισσότερο στρατιωτικό χαρακτήρα, όπως υποδεικνύουν οι στρατώνες που κατασκευάστηκαν κοντά στον μενδρεσέ και η γειτονική πυριτιδαποθήκη.

Η Λέσβος περιήλθε στο Ελληνικό κράτος στις 8 Νοεμβρίου του 1912. Το εντός των τειχών τμήμα συνέχισε να κατοικείται μέχρι και λίγο μετά τον Β΄ Παγκόσμιο Πόλεμο.

Από τη δεκαετία του '70 το κάστρο αποκτά τη λειτουργία μνημείου, επισκευάζεται και συντηρείται.