Το 15ο Δημ. Σχ. Μυτιλήνης ιδρύθηκε με το ΦΕΚ 992 τΒ’/31-07-2002. Τα πρώτα χρόνια της λειτουργίας του ήταν παράρτημα του 7ου Δημ. Σχ. Μυτιλήνης με το οποίο συστεγάζονται μέχρι σήμερα στον ίδιο ενιαίο χώρο οικοπέδου, αλλά σε ξεχωριστά κτίρια και με δική του αυλή το καθένα.
Με την με αριθ. πρωτ. 1153/23-04-2002 απόφαση του Δ/ντή Α/θμιας Εκπ/σης Λέσβου, το 7ο Δημ. Σχ. Μυτιλήνης και το 15ο Δημ. Σχ. Μυτιλήνης, λειτουργούν από το 2002 ως συστεγαζόμενα σχολεία σε διαφορετικά κτίρια.
Το καλοκαίρι του 2020 το 15ο Δημ. Σχ. Μυτιλήνης εντάχθηκε από τον Δήμο Μυτιλήνης σε πρόγραμμα ΕΣΠΑ ενεργειακής αναβάθμισης, το οποίο έχει ολοκληρωθεί. Το σχολείο διαθέτει κλειστό Γυμναστήριο που χρησιμοποιείται και ως Αίθουσα Τελετών, γήπεδο 5Χ5, και γήπεδο μπάσκετ-χάντμπολ.
