Το Γυμνάσιο Μυτιλήνης (τώρα 2ο ΓΕΛ- Πρότυπο Λύκειο Μυτιλήνης) ιδρύθηκε το 1840 με πρωτοβουλία του τότε Μητροπολίτη Μυτιλήνης Μελετίου Φωτίου (+ 1867) και με δωρεές πλουσίων Λεσβίων και άλλων Ελλήνων που αγαπούσαν την πατρίδα τους. Την ίδια περίοδο δημιουργήθηκε στο Γυμνάσιο και η ιστορική βιβλιοθήκη.
Τα χρόνια εκείνα η Λέσβος βρισκόταν κάτω από τουρκική κατοχή. Οι δυνατότητες για μόρφωση ήταν ιδιαίτερα περιορισμένες , αφού οι Τούρκοι δεν επέτρεπαν στους υπόδουλους Λέσβιους μεταξύ των άλλων , και να μορφωθούν. Ορισμένες όμως πολιτικές εξελίξεις που ξεκίνησαν στο εσωτερικό της Τουρκίας το 1839, έδωσαν τη δυνατότητα στους Έλληνες της Λέσβου να προχωρήσουν στην ίδρυση του Γυμνασίου Μυτιλήνης. Να σημειωθεί επίσης ότι το σχολείο πλήγηκε από τον καταστροφικό σεισμό του 1867. Το Γυμνάσιο αναγνωρίστηκε από την ελληνική κυβέρνηση το 1875 και λειτούργησε με την ίδια αρχιτεκτονική μορφή επί 48 χρόνια. Έπειτα, μετά από την απελευθέρωση της Λέσβου από τους Τούρκους το 1913 το Γυμνάσιο χρησιμοποιήθηκε ως στρατιωτικό νοσοκομείο. Το Γυμνάσιο Μυτιλήνης πήρε την ονομασία που έχει σήμερα δηλ. Πρότυπο Λύκειο Μυτιλήνης, και από το 1978-1979 πλέον συστεγάζεται με το 2 ο Γενικό Λύκειο Μυτιλήνης. Από το 1939 λειτούργησε ως Β΄Γυμνάσιο Αρρένων.
Την περίοδο 1888-1890 αποφασίστηκε να κτιστεί στον ίδιο περίπου χώρο ένα νέο επιβλητικό κτίριο (αυτό που μέχρι σήμερα υπάρχει) με εργαστήριο φυσικής, αίθουσα τελετών, βιβλιοθήκη και μουσείο με σχέδια του Λέσβιου αρχιτέκτονα Αργύρη Αδαλή, για την κατασκευή του οποίου απαιτήθηκε ποσό μεγαλύτερο από εκείνο που χρειάστηκε για την ανέγερση του πανεπιστημίου Αθηνών. Ο τελευταίος είχε την σπουδαία ιδέα να χρησιμοποιήσει δωρικό ρυθμό στο ισόγειο και ιωνικό στον πάνω όροφο. Στην ολοκλήρωση του έργου συνέβαλε σημαντικά ένας σημαντικός Λέσβιος, ο Σοφοκλής Βουρνάζος, ο ανδριάντας του οποίου βρίσκεται σήμερα (από το 1896) στον μπροστινό χώρο του σχολείου.