Σύμφωνα με την τοπική παράδοση το τοπωνύμιο Παναγία προϋπήρχε του χωριού και προήλθε από κάποιο παλιό μοναστήρι. Ως τα μέσα του 19ου αιώνα στην περιοχή της Β. Α. Λήμνου ανάμεσα στο χωριό Κοντοπούλι και στο ακρωτήριο Πλάκα δεν υπήρχε χωριό. Υπήρχαν μόνο μερικές απομονωμένες καλύβες τσιφλικιών, που ανήκαν σε Τούρκους αγάδες του Ανυπάτη. Το χωριό Παναγία ιδρύθηκε γύρω το 1865 από κατοίκους του Αγίου Υπατίου και του Κοντοπουλίου που είχαν κτήματα στην περιοχή. Ως πρώτοι οικιστές θεωρούνται οι, Κομνηνός Κατωγούδης, Ιωάννης Λαγός, Εμμανουήλ Παξιμαδάς, Δημήτριος Τσαγδής και Ιωάννης Κεχαγιάς. Επιλέχθηκε η θέση «Παναγία», όπου βρισκόταν η παλιά βυζαντινή μονή, στους πρόποδες του λόφου «Αλεπότρυπες», πιθανόν επειδή βρισκόταν σε ίση περίπου απόσταση από τις δυτικές και τις ανατολικές ακτές, άρα παρείχε μεγαλύτερη ασφάλεια.