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

Η ιδέα να στεγαστεί στο κτίριο αυτό το Αρχαιολογικό Μουσείο συζητήθηκε για πρώτη φορά στα 1930. Οι προσπάθειες όμως σταμάτησαν εξαιτίας της αναταραχής που προκάλεσαν τα προμηνύματα του Β' παγκοσμίου πολέμου.

Στα 1939 το κτίριο πουλήθηκε από την κοινότητα Κάστρου (σημερινός Δήμος Μύρινας) στο Παλλημνιακό Σχολικό Ταμείο, με τον όρο να δωρηθεί στο Δημόσιο για να στεγάσει το Αρχαιολογικό Μουσείο Λήμνου.

Το κτίριο του Μουσείου επισκευάστηκε το 1956. Στα χρόνια του Β' παγκοσμίου πολέμου τα αρχαιολογικά ευρήματα της Λήμνου μεταφέρθηκαν στο Μουσείο Μυτιλήνης και στο Εθνικό Αρχαιολογικό Μουσείο στην Αθήνα, για να φυλαχθούν , και επέστρεψαν στη Λήμνο το 1961, μετά την ολοκλήρωση των επισκευών. Οι εργασίες επανέκθεσης τελείωσαν το 1961.

Στις αρχές της δεκαετίας του 1990 επισκευάστηκε ξανά το κτίριο και το 1993 άνοιξε η νέα επανέκθεση.

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