West of the village, in a small port near Cape Sotiras, an ancient site has been found. At the southern end of the bay a stele from the 4th century BC has been found, that reads: BENDIDORA METROPHANOU GERGISIOU. In medieval texts the location was mentioned as the valley of Saint Saviour. The map of the Italian traveller Buondelmonti (1418) mentions a chapel Sotira. A coastal settlement known as Sotira in northeastern Lemnos was mentioned on maps of other travellers including Belon (1588) and Dapper (1688). In 1858, when Conze visited the cape and the bay of Sotiras, he observed an old ruined stone pier and the chapel of Agios Sotiras.

By the mid 19th century, there were no villages in the area of northeast Lemnos between Kontopouli and the cape Plaka. There were only a few isolated farms, which belonged to Turkish land owners from Agios Ypatios. The village of Panagia was founded around 1865 by residents of Agios Ypatios and Kontopouli that owned land in the area. The location of Panagia was chosen because of its equal distance to the east and west coast of the peninsula, providing greater safety. At Panagia an old Byzantine monastery was situated, at the foot of the hill Alepotrypes (Αλεπότρυπες).

In 1874, it had 30 families. In another work of the same year, Panagia was mentioned as Tsiftlikia (Τσηφτλίκια). Apparently the name Panagia was not in use yet. It was first mentioned on a map in 1904 by Fredrich, together with the two nearby settlements Naxia and Petsa. In 1865, the first inhabitants built a church of Panagia (Our Lady) in the location of the old monastery. Later they built a newer church with a gift of $6,500 from Anastasios Diamantis, an immigrant from the USA. In 1887, a community school was founded in nearby Plaka, which also served pupils from Panagia. In 1903, a school was founded in Panagia. The school building was built between 1929 and 1932.

In spite of being situated in a remote part of Lemnos, the village grew between World Wars I and II, because several refugee families from Asia Minor settled there. The fertility of the soil also contributed to the growth, and in 1928 Panagia had 406 inhabitants. After World War II, the agricultural fields produced 407 tons of cotton and 700 tons of wheat. In 1961, it had 697 inhabitants. Later the population declined, but it is still one of the most lively villages on the island. It has a fishing club, a soccer club and an active cultural council.

• Tourtsopoulou-Stefanidou Vasilili, Ταξιδιωτικά και γεωγραφικά κείμενα για τη νήσο Λήμνο (15ος-20ος αιώνας) = Travelling and Geographic Sources of Lemnos Island (15th-20th Centuries) Thessaloniki, 1986.
• Lemnos CD: Λήμνος αγαπημένη = Loveable Lemnos
• Theodoros Belitsos, Η Λήμνος και τα χωριά της = Lemnos and its villages, 1994

• List of settlements in the Lemnos regional unit