Βυζαντινή αυτοκρατορία (13ος-15ος αι.)
13ος Αιώνας
Μετά την διάλυση του Μεγάλου Δουκάτου της Λήμνου το 1279 από τον Λατίνο ναύαρχο του Βυζαντίου Λυκάριο, η Λήμνος παρέμεινε στη δικαιοδοσία των Παλαιολόγων αυτοκρατόρων μέχρι το τέλος της Βυζαντινής Αυτοκρατορίας. Η διατήρηση βέβαια της Λήμνου στην αυτοκρατορία επιτεύχθηκε με πολλές δυσκολίες και αγώνες, όχι μόνο επειδή λόγω της σημαντικής γεωγραφικής θέσης της η Λήμνος ήταν ένα πολυπόθητο ζητούμενο μεταξύ των κατακτητών και ιδιαίτερα των Λατίνων και των Οθωμανών, αλλά και επειδή η ίδια αυτοκρατορία ήταν αποδυναμωμένη από εσωτερικές έριδες και εξωτερικές επιθέσεις και αδυνατούσε να υπερασπιστεί τα εδάφη της. Το νησί υπέστη πολλές καταστροφές και λεηλασίες σε σημείο ερήμωσης και οι κάτοικοί του έζησαν πολλές συμφορές και αιχμαλωσίες από πολλές επιδρομές, με χαρακτηριστικά παραδείγματα την επιδρομή το 1292 από τον ναύαρχο του βασιλείου της Σικελίας Ρουγκέρο ντι Λαουρία (Ruggero di Lauria), το 1296 από τον Βενετό Μαλαμπράνκα (Malabranca) και το 1304 από την Καταλανική Εταιρία. Στην περίοδο 1306-1309 και για λίγο το 1377 οι Βενετοί κατέλαβαν την Λήμνο και την λεηλάτησαν ενώ η δεινή θέση της από παντού βαλλόμενης Βυζαντινής Αυτοκρατορίας επιδεινωνόταν και από την εξάπλωση των Οθωμανών εις βάρος των εδαφών της. Όσο περισσότερο συρρικνωνόταν η αυτοκρατορία τόσο περισσότερο επιτακτική ήταν η ανάγκη προστασίας των νησιωτικών κτήσεων, διατήρησης ισχυρών φρουρίων και σημαντικής στρατιωτικής δύναμης σε αυτές τις κτήσεις. Στην Λήμνο υπήρχαν κάστρα σε αρκετές τοποθεσίες, Μύρινα, Κότσινα, Μούδρο, Σκάλα (Φισίνη), Πλάκα, κ.ά., και διάσπαρτοι στο νησί παρατηρητήρια-πύργοι. Τις οχυρώσεις αυτές τις συντηρούσαν, επισκεύαζαν και υπεράσπιζαν οι πολιτικοί άρχοντες, οι κάτοικοι και τα εκκλησιαστικά ιδρύματα του νησιού.
Ο περιηγητής Χριστόφορο Μπουοντελμόντι (Christoforo Buondelmonti), όταν πέρασε από το νησί στο τέλος της 2ης δεκαετίας του 15ου αιώνα, το πιθανότερο το 1418, αναφέρει ότι υπήρχαν πολλές οχυρές πόλεις, κάτι που διαπιστώνεται και από τα μοναστηριακά έγγραφα της εποχής από τα οποία φαίνεται ότι ανάμεσά στις οχυρές πόλεις συγκαταλεγόταν και η Μύρινα.
14ος Αιώνας
Το 1361 μέσα στο κλίμα των εχθρικών επιδρομών και της αστάθειας και κατά την διάρκεια της βασιλείας του αυτοκράτορα Ιωάννη Ε΄ Παλαιολόγου, πραγματοποιήθηκαν στο κάστρο επιδιορθωτικές και ενισχυτικές εργασίες, όταν διοικητής του νησιού ήταν ο Γεώργιος Συναδηνός Άστρας. Επιπλέον, ενισχύθηκε η κεντρική είσοδος του κάστρου με την προσθήκη στα ανατολικά μιας επιπλέον πύλης πλαισιωμένη με πύργους που φέρουν επάλξεις. Με αυτόν τον τρόπο διαμορφώθηκε η σημερινή κάτοψη του χώρου της κεντρικής πύλης που αποτελείται από τεθλασμένο διάδρομο τριών τμημάτων και από τρία θυρώματα. Στον ίδιο χώρο πραγματοποιήθηκαν αργότερα το 1394 και άλλες ενισχυτικές εργασίες σύμφωνα με την χρονολόγηση μαρμάρινης ανάγλυφης πλάκας που υπήρχε εντοιχισμένη στο αντέρεισμα του ανατολικού περιβόλου, εσωτερικά του χώρου της κεντρικής πύλης και απέναντι από αυτήν. Η πλάκα, που λέγεται ότι υπήρχε εντειχισμένη στο τείχος έως το 1982 (και τώρα βρίσκεται στο Αρχαιολογικό Μουσείο Μύρινας), έχει διαστάσεις 0,76χ 0,36 χ 0,25μ., φέρει στο κέντρο της το μονόγραμμα των Παλαιολόγων ενώ αριστερά και δεξιά τα γράμματα Θω και Μ, τα οποία ερμηνεύονται ως Θεόδωρος και Μανουήλ αντίστοιχα. Ο τύπος της αναμνηστικής πλάκας και οι λεπτομέρειές της παραπέμπουν στον Θεόδωρο Παλαιολόγο (θείο του τότε αυτοκράτορα Μανουήλ Β’ Παλαιολόγου), που ήταν διοικητής της Λήμνου το 1394 και στον Μανουήλ Εσκαμματισμένο, ο οποίος πιθανόν να διαχειριζόταν την στρατιωτική εξουσία.
Φαίνεται ότι υπήρχε σημαντικού μεγέθους πρόγραμμα ενισχυτικών εργασιών, τουλάχιστον στα δυο φρούρια του νησιού, του κάστρου της Μύρινας και του Κότσινα. Σύμφωνα με μοναστηριακά έγγραφα, το έτος 1376 ο αυτοκράτορας Ιωάννης Ε΄ απευθύνθηκε με επιστολή στους ηγούμενους των αθωνικών μονών ζητώντας τους να βοηθήσουν στις κατασκευαστικές και οχυρωτικές εργασίες, ειδικότερα με ξυλεία και δυο μαστόρους, τον πρωτοστάτη Μακάριο Γλαβά Ταρχειωνίτη, ο οποίος είχε σταλεί στην Λήμνο για να διευθύνει την επανοχύρωση των φρουρίων της Μύρινας και του Κότσινα. Η μέριμνα αυτή φανερώνει πόσο σημαντική θεωρούσαν οι Βυζαντινοί την κατοχή του κάστρου για την διατήρηση του νησιού κάτω από την κυριαρχία τους. Πιθανόν στο διάστημα αυτής της περιόδου των ενισχυτικών εργασιών, να ενισχύθηκε επί πλέον η οχύρωση στα βόρεια της χερσονήσου με την κατασκευή του βόρειου εξωτερικού τείχους κοντά στην ακτή, ώστε να γίνεται λόγος για τριπλό τείχος.
15ος Αιώνας
Ο ιστορικός Κριτόβουλος ο Ίμβριος στο Γ΄ βιβλίο του (85, 2-3) εξιστορώντας τα γεγονότα του έτους 1459 περιγράφει την ακρόπολη και το κάστρο της Μύρινας αναφέροντας την ύπαρξη πολύ παλιού τριπλού τείχους: «Έστι γάρ ή τῆς Μιρηνοῡ πόλεως ακρόπολις έχυρωτάτη καί πάντη άνεπιχείρητος καί τῶν ονομαστῶν έπ' άσφαλεία έκ πάνυ παλαιοῡ, έπ' άκρας τε ύπεράνω κτισμένη τῆς πόλεως έφ’ ύψηλοῡ καί τριπλώ τείχει παλαιοτάτω καί λίθοις μεγίστοις κατησφαλισμένη τε καί κατωχυρωμένη, και πᾶσαν ύπ’ αυτήν έχουσα καί καταδουλοῡσα τήν πόλιν».
Στο κάστρο της Μύρινας θάφτηκε και η σύζυγος του τελευταίου βυζαντινού αυτοκράτορα Κωνσταντίνου ΙΑ΄Παλαιολόγου, η Αικατερίνη Γατελούζη, η οποία απεβίωσε μετά από επιπλοκές της εγκυμοσύνης το 1442 κατά την διάρκεια τουρκικής πολιορκίας του κάστρου του Κότσινα, όπου είχαν καταφύγει με τον αυτοκράτορα στο δρόμο τους από την Μυτιλήνη για την Κωνσταντινούπολη για να αποφύγουν τον τουρκικό στόλο που βρισκόταν στην περιοχή.
Λέγεται ότι η λεγόμενη πυριτιδαποθήκη στα βορειοανατολικά της κεντρικής πύλης ίσως να ήταν το μαυσωλείο της, αλλά το αληθές της εικασίας μόνο με ανασκαφική έρευνα και μελέτη μπορεί να τεκμηριωθεί.
Αναμφίβολα κάποια από τα μαρμάρινα μέλη που βλέπουμε σήμερα ενσωματωμένα στα τείχη του κάστρου προέρχονται από αυτή την περίοδο της βυζαντινής κυριαρχίας. Όπως αναφέρθηκε και σε άλλο κεφάλαιο (κλασική-ελληνιστική-ρωμαϊκή αρχαιότητα), αρκετοί περιηγητές όπως ο Τόζερ (Tozer), και αρχαιολόγοι ιστορικοί, όπως ο Σίλι (Sealy) και ο Καρλ Φρέντριχ (Carl Fredrich), κατά την επίσκεψή τους στο κάστρο τον 19ο και αρχές του 20ού αιώνα, είχαν εντοπίσει και μνημονεύσει κατάλοιπα-μάρτυρες του αρχαίου παρελθόντος, όπως κομμάτια μαρμάρινων κιόνων, βάσεις κιόνων και άλλα μαρμάρινα αρχιτεκτονικά μέλη ενσωματωμένα στα τείχη του κάστρου. Ο Γερμανός αρχαιολόγος Καρλ Φρέντριχ (Carl Fredrich), κατά την επίσκεψή του στο κάστρο το 1904, είχε εντοπίσει στα τείχη επισκευές και ανανεώσεις από την ελληνιστική, ρωμαϊκή και μεταγενέστερη εποχή καθώς και πολλά μαρμάρινα αρχαία μέλη ενσωματωμένα στα τείχη.