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

Εκτός από τους δύο βασικούς ορόφους υπάρχει και ισόγειο για βοηθητική χρήση. Οι δύο κύριοι όροφοι χωρίζονται σε πολλά δωμάτια με διάδρομο στη μέση και επικοινωνούν μεταξύ τους με ξύλινη κλίμακα. Στον πρώτο όροφο οδηγεί από την αυλή διπλή πέτρινη κλίμακα.

Η ιδέα να στεγαστεί στο κτίριο αυτό το Αρχαιολογικό Μουσείο συζητήθηκε για πρώτη φορά στα 1930. Οι προσπάθειες όμως σταμάτησαν εξαιτίας των αναταραχών που προκάλεσαν τα προμηνύματα του Β' παγκοσμίου πολέμου. Το 1939 το κτίριο πουλήθηκε από την κοινότητα Κάστρου (σημερινός Δήμος Μύρινας) στο Παλλημνιακό Σχολικό Ταμείο, με τον όρο να δωρηθεί στο Δημόσιο για να στεγάσει το Αρχαιολογικό Μουσείο Λήμνου. Κατά την γερμανική κατοχή το κτίριο έπαθε μεγάλες καταστροφές και άρχισε να επισκευάζεται το 1956. Οι εργασίες ολοκληρώθηκαν το 1959 και το 1961 έγινε η επανέκθεση.

Νέες επισκευές στο κτίριο έγιναν στις αρχές της δεκαετίας του 1990 και το 1993 έγιναν τα εγκαίνια της νέας έκθεσης, η οποία φιλοξενείται ως σήμερα.

Το κτίριο του Μουσείου βρίσκεται σε μικρή απόσταση από το κάστρο της πόλης της Μύρινας και μαζί μ' αυτό αποτελούν έναν ενιαίο αρχαιολογικό χώρο.