Το πρώτο Μουσείο της Μυτιλήνης χτίστηκε από την Αμερικανική Σχολή Κλασικών Σπουδών στη θέση Κιόσκι της Μυτιλήνης το 1935. Το 1963 παρουσίασε ρωγμές λόγω της καθίζησης του εδάφους και ο τότε Έφορος Αρχαιοτήτων Σ. Χαριτωνίδης αναγκάστηκε να μεταφέρει τα βαριά μαρμάρινα και λίθινα αντικείμενα σε περιφραγμένο χώρο δίπλα στο κτίριο του Μουσείου και τα πήλινα στο κτίριο της παλαιάς Νομαρχίας σε νοικιασμένο χώρο.

Το 1965 αγοράστηκε από το ΥΠ.ΠΟ, το επί της οδού Α. Εφταλιώτη 7, κτίριο με το υποστατικό και τον αύλειο χώρο της ιδιοκτησίας Βουρνάζου, (κατασκευασμένο το 1912 με σχέδια του αρχιτέκτονα Βαφειάδη από τη Σμύρνη), όπου βρίσκεται το σημερινό Παλαιό κτίριο. Εκεί, τότε, μεταφέρθηκαν τα πήλινα αντικείμενα και μέρος των μαρμάρινων ενώ τα υπόλοιπα λίθινα τοποθετήθηκαν στην αποθήκη του Κάτω Κάστρου.

Το 1967 έγινε έκθεση στο παραπάνω κτίριο, η οποία τροποποιήθηκε το 1974. Το 1985 στο κτίριο εγκαταστάθηκε το Υπουργείο Αιγαίου και τα λίγα αρχαία που ήταν εκτεθειμένα φυλάχτηκαν στα υπόγεια του κτιρίου.

Τον Αύγουστο του 1990 επεστράφη το κτίριο του Μουσείου στο ΥΠ.ΠΟ με μεγάλες φθορές, ενώ το υποστατικό του αρχοντικού είχε επισκευαστεί από το ΥΠ.ΑΙ για να καλύψει τις ανάγκες στέγασης του προσωπικού του. Αμέσως άρχισε η οργάνωση της έκθεσης των αρχαιοτήτων της Λέσβου και η επισκευή του κτιρίου, στα μέτρα του δυνατού, με το μόνιμο προσωπικό της Εφορείας.

Η έκθεση που εγκαινιάστηκε στις 13 Ιουλίου 1991 είναι η ίδια που υπάρχει και σήμερα. (Μόνιμη έκθεση στο Παλαιό κτίριο του Αρχαιολογικού Μουσείου Μυτιλήνης)

Οι ανάγκες στέγασης του πλήθους των αρχαιολογικών ευρημάτων που έρχονταν στο φώς κατά τη διάρκεια των ανασκαφικών ερευνών στην πόλη της Μυτιλήνης αλλά και της περιφέρειας της Λέσβου οδήγησαν στην κατασκευή ενός Νέου κτιρίου, το οποίο μαζί με το Παλαιό θα έδιναν μια πληρέστερη εικόνα της καθημερινής ζωής στην αρχαία Λέσβο.

Η κατασκευή του Νέου κτιρίου ξεκίνησε το 1984 και ολοκληρώθηκε το 1995 με τη συγχρηματοδότηση του Ελληνικού κράτους και της Ευρωπαϊκής Ένωσης. Η μελέτη για την κατασκευή του εκπονήθηκε από ομάδα αρχιτεκτόνων του Ε.Μ.Π με επικεφαλή τον Φ. Γουλιέλμο.

Το 1995 πραγματοποιήθηκαν τα εγκαίνια του κτηρίου μαζί με την πρώτη περιοδική έκθεση του Νέου Μουσείου, η οποία έφερε τον τίτλο "Λέσβος Μακαρία".

Το 1999 έγιναν τα εγκαίνια της μόνιμης έκθεσης του Μουσείου με τίτλο "Η Λέσβος από την ελληνιστική στη ρωμαϊκή εποχή" και ταυτόχρονα της νέας περιδικής έκθεσης, η οποία αντικατέστησε την προηγούμενη και η οποία έφερε τον τίτλο " Οι νεκροπόλεις της Λέσβου".

Τον Φεβρουάριο του 2001 η περιοδική αντικαταστάθηκε με νέα έκθεση, η οποία φιλοξενείται εως σήμερα και φέρει τον τίτλο "Ένα λουκούλλειο γεύμα". Η παραπάνω στηρίχτηκε στα ευρήματα που ήρθαν στο φως κατά τη διάρκεια του βιολογικού καθαρισμού στην πόλη της Μυτιλήνης και συγκεκριμένα σε κτιστή ιχθυοδεξαμενή ρωμαϊκών χρόνων.

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