Το χωριό πρωτοαναφέρεται ως ένας από τους 25 οικισμούς της Λήμνου που αποτελούσαν πατριαρχική εξαρχία το 1321. Σύμφωνα με την παράδοση το χωριό έκτισε ο ηγούμενος Σκανδάλιος κάποιου κοντινού μοναστηριού. Κάποια άλλη παράδοση αναφέρει ότι ένας ξενομερίτης που εγκαταστάθηκε στην περιοχή κατάφερε με σκανδαλώδη τρόπο, με απάτες και ραδιουργίες, να αναδειχθεί άρχων του τόπου και οι κάτοικοι τον αποκαλούσαν Σκανδάλη. Τότε το χωριό βρισκόταν χίλια μέτρα δυτικότερα, στη θέση Δρυ, όπου σήμερα εντοπίζονται ερείπια και το εκκλησάκι του Αγ. Κωνσταντίνου. Όταν κάποιος σεισμός κατάστρεψε το παλιό χωριό, ο Σκανδάλης πρωτοστάτησε στη μεταφορά του στη σημερινή θέση κι έτσι στο νέο χωριό δόθηκε το όνομά του. Παρατηρούμε, πως κι οι δυο παραδόσεις συγκλίνουν στο ότι το όνομα του χωριού προήλθε από το όνομα του ιδρυτή του.
Στο χωριό υπάρχουν τέσσερις ναοί με πολιούχο τον Άγιο Νικόλαο, που χτίστηκαν περίπου το 1880. Το χωριό έχει καλό κλίμα και άφθονα νερά, γι’ αυτό στην εύφορη πεδιάδα που απλώνεται προς τα νότια εγκαταστάθηκε το ιππικό των συμμάχων κατά τον Α’ παγκόσμιο πόλεμο. Ακόμα σώζονται οι τεράστιες στέρνες που φτιάχτηκαν για την αποθήκευση νερού.