Die Burg von Mytilene, eine der größten und bedeutendsten im Mittelmeerraum, befindet sich auf dem höchsten Punkt des nordöstlichen Endes der Halbinsel, wo einst die antike Akropolis errichtet wurde. Sie nimmt ein Gebiet von 300 m Länge und 150-270 m Breite ein, das sich von der Spitze des Hügels bis zum nordwestlichen Hang erstreckt und bis zum nördlichen Hafen reicht.
Ihre erste Bauphase geht auf die byzantinische Zeit zurück (wahrscheinlich im 6. Jh. n. Chr.), aus der einige Teile mit dem charakteristischen Mauerwerk der Epoche und reichlich antikes Baumaterial erhalten sind, das in einer zweiten Phase wiederverwendet wurde. Ihre heutige Form ist das Ergebnis drastischer Eingriffe vor allem durch das genuesische Haus Gattilusio, das die Insel während der spätbyzantinischen Zeit (1355-1462) beherrschte, aber auch durch die Osmanen, die Lesbos von 1462 bis 1912 besetzten.
In der osmanischen Zeit wurde entlang der südöstlichen und südwestlichen Hauptmauer eine Außenmauer errichtet und mit Rundtürmen verstärkt, wie es die neue Kriegstaktik und der umfangreiche Einsatz von Schießpulver erforderten, während gleichzeitig ein Graben angelegt wurde. Im Jahr 1501 wurde Kato Kastro (Untere Burg) errichtet, das sich ungefähr an der gleichen Stelle befand wie die frühere befestigte Siedlung Melanoudi.
Die Festung von Mytilene besteht aus drei Teilen: der Oberen Burg (Epano oder Ano Kastro) auf der Spitze des Hügels, der Mittleren Burg (Meseo Kastro) am nordwestlichen Hang und der Unteren Burg (Kato Kastro) auf der unteren Ebene neben dem nördlichen Hafen.
Durch das südliche Doppeltor gelangt man in einen länglichen rechteckigen Hof, an dessen nordwestlichem Ende sich ein älterer byzantinischer Hof befindet. Rechts vom Eingang, am östlichen Ende der Festung, befindet sich der am stärksten befestigte Teil der Burg, den sogenannten “Megalos Perivolos“ (Seitenturm), der durch fünf quadratische Türme und einen Graben an der Nordwest- und Südwestseite geschützt war. Der Seitenturm umfasste einen Innenhof, zwei Räume im Osten und ein Pulvermagazin im Nordwesten, das später von den Osmanen, an der Stelle der früheren genuesischen Loggia errichtet wurde. Westlich des Seitenturms befindet sich das Heiligtum der Demeter und Tochter (mit gleichzeitiger Anbetung der Kybele), das von der langen Kontinuität der Nutzung der Anlage zeugt. Südlich des Heiligtums befindet sich die Kule-Moschee, die von den Osmanen an der Stelle der früheren byzantinischen Kirche von Agios Ioannis aus der Zeit der Gattilusio errichtet wurde. In der südwestlichen Ecke der Oberen Burg (Epano Kastro) befinden sich die Krypten, ein großer unterirdischer Bereich, der im Notfall zum Schutz der Bevölkerung dienen sollte.
Der Zugang zu Meseo Kastro (Mittlere Burg) erfolgte durch das so genannte Mittlere Tor (auch “Orta Kapou“ genannt) im Südwesten, das ein späterer Beitrag der Osmanen ist. Im Inneren befindet sich das älteste Tor aus der Zeit der Gattilusio, gefolgt von einem dritten Tor und einem viereckigen Turm aus der byzantinischen Zeit. In der Mittleren Burg wurden die wichtigsten religiösen und weltlichen Gebäude aus der osmanischen Zeit errichtet. Im östlichen Teil befinden sich die Medrese (islamische Lehreinrichtung), das Hamam (Bad) oder die Zisterne, die Tekke (osmanisches Kloster), das Gefängnis, das später als Militärkrankenhaus diente, ein zweites Pulvermagazin sowie ein Häuserkomplex. Im westlichen Teil befinden sich ein osmanisches Haus, ein Brunnen aus der gleichen Zeit und auch die Zisterne.
Im Jahr 1501 errichteten die Osmanen die Untere Burg (auch “Saplitza“ genannt), die hauptsächlich dem Schutz des nördlichen Hafens diente. Der Zugang zu ihr erfolgte durch das nördliche Tor, einem Doppeltor mit Zwischenhof. In der Unteren Burg (Kato Kastro) befinden sich ein zweiter osmanischer Brunnen und ein zweites osmanisches Bad (Hamam) aus dem 17. Jahrhundert, und neben den zahlreichen osmanischen Häusern und den berühmten osmanischen Orakeln befand sich in diesem Gebiet auch eine frühchristliche Gebetshöhle mit dem Heiligtum/Kapelle der Panagia Galatusa. Der Nordwestteil von Kato Kastro ist heute ein Aufbewahrungsort für antike Gegenstände.
Nach der Befreiung von Lesbos im Jahr 1912 wurde die Festung von Mytilene ausschließlich zu Wohnzwecken genutzt, während sie 1922 mit der kleinasiatischen Katastrophe einen ersten schweren Schlag erlitt, da ein Großteil ihres Baumaterials für den Bau der ersten Flüchtlingsunterkünfte verwendet wurde. Ab den 1960er Jahren wurden von den jeweiligen Ephorien für Altertümer systematische Maßnahmen zur Erhaltung, Restaurierung, Förderung und Verbesserung des Zustands der Festung ergriffen. Im Jahr 2018 schloss die Ephorie für Altertümer von Lesbos die Arbeiten zur Sicherung und Restaurierung von Teilen der nordöstlichen Außenmauer der Festung ab, während der gesamte Bereich von Kato Kastro bis heute weiter ausgebaut wird.