Τ όνομα του χωριού πρωτοαναφέρεται σαν ένα από τα 25 χωριά της Λήμνου που αποτελούσαν πατριαρχική εξαρχία το 1321.

Δωρήθηκε στο Πατριαρχείο από κάποιον γεωκτήμονα, τον Σκανδάλη. Τ' όνομα αυτό είναι βυζαντινό και προέρχεται από τη λέξη "σκάνδαλο = άτοπη ενέργεια". Σύμφωνα με την τοπική παράδοση το χωριό πρωτοκτίστηκε από τον ηγούμενο κάποιου γειτονικού μοναστηριού, που λεγόταν Σκανδάλιος.

Μια άλλη παραλλαγή της προφορικής παράδοσης αναφέρει ότι το χωριό αρχικά βρισκόταν στη θέση Δρυ στα Β.Δ. του σημερινού και σε απόσταση 1.000 μ. Κάποτε εγκαταστάθηκε στο χωριό κάποιος ξενομερίτης, ο οποίος κατάφερε με απάτες και ραδιουργίες να ηγεμονεύσει και να γίνει προύχοντας. Γι' αυτό οι χωριανοί τον ονόμασαν Σκανδάλη. Γύρω από τα κτήματα του, που βρισκόντουσαν στη σημερινή θέση του χωριού, δημιουργήθηκε οικισμός που ονομάστηκε του Σκανδάλη, που είναι και η σωστότερη εκφορά του ονόματος του χωριού.
Επί τουρκοκρατίας άλλοτε αναγράφεται σαν "η Σκανδάλη" και άλλοτε σαν "το Σκανδάλι ή Σκαντάλι". Στου Σκανδάλη λειτούργησε το πρώτο σχολείο της Ν.Α. Λήμνου, το 1848, σε κτίριο που δώρησε ο Ιωάννης Δουκαρέλλης (αιγυπτιώτης μετανάστης).
Στην περιοχή της Αγ. Ειρήνης, νοτιότερα απ' του Σκανδάλη, αναφέρεται το 1680 από τον Piacenza ο άγνωστος οικισμός Carfa.