Το σχολικό έτος 1884-85 το Γυμνάσιο έχει συνολικά 259 μαθητές, αριθμός αρκετά υψηλός. Το κτίριο λόγω παλαιότητας και εξαιτίας των φθορών του καταστρεπτικού σεισμού του 1867 δεν εξυπηρετούσε πλέον τις αυξημένες ανάγκες τις εποχής. Έτσι με επιστολή που συνυπογράφεται από τη Δημογεροντία και τη Σχολική Εφορία προς το Μουτεσαρίφη Μυτιλήνης Φαχρή Βέη, κοινοποιείται η απόφαση για ανέγερση καταλληλότερου εκπαιδευτηρίου που θα πληροί τις νέες αυξημένες ανάγκες. Από τη δωρεά του Μεγάλου Ευεργέτη Ν. Μητρέλια αποτελούμενη από 7 χιλιάδες λίρες και από τη διαθήκη του Σοφοκλή Βουρνάζου από 20 χιλιάδες λίρες θα χρηματοδοτηθεί το όλο έργο. Με τη βοήθεια του Μητροπολίτη Μυτιλήνης, Κωνσταντίνου Βαλιάδη στην Κωνσταντινούπολη, που πήγε ειδικά γι’ αυτό το σκοπό, και του καπουκεχαγιά (αρχιθυρωρού) των Ανακτόρων Σταυράκη Εφέντη, γρήγορα θα εκδοθεί το σχετικό Αυτοκρατορικό φιρμάνι για την ανέγερση του νέου Γυμνασίου, το Σεπτέμβριο του 1886. Το νέο Γυμνάσιο οικοδομήθηκε με σχέδιο του αρχιτέκτονα Αργύρη Αδαλή στη θέση του παλιού. Άρχισε να χτίζεται το 1887. Το θεμέλιο λίθο έβαλε στις 30/8/1887 ο πρώην Πατριάρχης Αλεξανδρείας Καλλίνικος, ο Διοικητής, ένα μέλος της οικογένειας Μητρέλια, ο πρόεδρος της Εφορίας και ο Δήμαρχος. Ο πρόεδρος της Εφορίας, Δ. Βερναρδάκης, εκφώνησε τον κατάλληλο για τις περιστάσεις λόγο. Θα χρησιμοποιηθούν τα καλλίτερα υλικά. Μάρμαρα από την Τήνο και Πεντέλη, τζάμια από τη Γενεύη και την Κωνσταντινούπολη, ξυλεία από τον Πόντο. Το νέο καλλιμάρμαρο κτίριο θα καλύψει έκταση 1.800 τ.μ. με ρυθμό δωρικό στο ισόγειο και ιωνικό στο ανώγειο. Στον πρώτο όροφο βρισκόταν το εφορείο των Φιλανθρωπικών και Εκπαιδευτικών Καταστημάτων Μυτιλήνης, το γραφείο του διευθυντή, οι αίθουσες διδασκαλίας και το εργαστήριο της Φυσικής το οποίο αναδιοργανώθηκε το 1896 με την έλευση του Μιχ. Στεφανίδη. Στο δεύτερο όροφο ήταν η αίθουσα τελετών, η βιβλιοθήκη και το μουσείο. Δεξιά του Γυμνασίου θα κατασκευαστεί επίσης ένα σύγχρονο Γυμναστήριο. Τα εγκαίνια του νέου περικαλλούς Γυμνασίου έγιναν στις 18-9-1891 από τον Μητροπολίτη Μυτιλήνης Κωνσταντίνο.
Τον Απρίλιο του 1894 θα σταλεί πατριαρχική επιστολή προς το Μητροπολίτη Μυτιλήνης που ζητούσε μετά το τέλος των εξετάσεων την απομάκρυνση του Γρηγ. Βερναρδάκη. Η απόφαση αυτή του Πατριαρχείου που είχε την εποπτεία στα θέματα εκπαίδευσης στην Οθωμανική Αυτοκρατορία, επιβάλλεται με τεσκερέ της Κυβέρνησης. Παρά την αντίθετη άποψη του συνόλου σχεδόν της Σχολικής Εφορίας ο Γρηγ. Βερναρδάκης θα οδηγηθεί σε παραίτηση τον Ιούλιο του 1894. Η παραίτηση του Γρηγορίου θα προκαλέσει μεγάλη συγκίνηση και λύπη στην κοινή γνώμη γιατί, αν και αυστηρός, τυπικός στην εκτέλεση των καθηκόντων του, το Γυμνάσιο επί των ημερών του απέκτησε τη φήμη ενός από τα καλύτερα του υπόδουλου Ελληνισμού.
Το Βερναρδάκη αντικατέστησε στη διεύθυνση των Σχολείων της Μυτιλήνης ο επιφανής φιλόλογος Πέτρος Παπαγεωργίου, άριστος σχολιαστής των αρχαίων Ελλήνων συγγραφέων, με μεγάλη μόρφωση αλλά κυρίως ανοικτός σε νεώτερες παιδαγωγικές ιδέες. Αυτό θα φανεί πρακτικά με την προώθηση των μαθημάτων της Φυσικής Πειραματικής, Χημείας και Φυτολογίας. Θα παραγγελθούν όργανα φυσικής και χημείας, προπλάσματα για την ανθρωπολογία, χάρτες για την διδασκαλία της Ιστορίας, Γεωγραφίας, Ανθρωπολογίας.
Το Γενάρη του 1896 έγιναν τα αποκαλυπτήρια του ανδριάντα του Σοφοκλή Βουρνάζου. Το άγαλμα φιλοτεχνήθηκε από το διακεκριμένο γλύπτη Γ. Μπονάνο. Κόστισε 20 χιλ. δρ. και χρησιμοποιήθηκε πεντελικό μάρμαρο αρίστης ποιότητας. Τα αποκαλυπτήρια του αγάλματος έκανε ο Δήμαρχος Μυτιλήνης Φώτιος Σιμωνίδης. Τον πανηγυρικό λόγο θα εκφωνήσει ο Γυμνασιάρχης στα προπύλαια του Γυμνασίου. Δημιουργός του επιγράμματος του αγάλματος ήταν ο Δ. Βερναρδάκης. Ας σημειωθεί επίσης ότι ήταν το πρώτο άγαλμα Έλληνα που στήθηκε στην Τουρκία.
Για την εξοικονόμηση ωρών διδασκαλίας της Γαλλικής γλώσσας στις τρεις τάξεις του Ελληνικού Σχολείου ο Γυμνασιάρχης πρότεινε στη Σχολική Εφορία το τετρατάξιο Γυμνάσιο, τριτάξιο Ελληνικό Σχολείο και το τετρατάξιο δημοτικό να καταργηθούν και να αντικατασταθούν με την εξατάξιο Αστική Σχολή και το εξατάξιο Γυμνάσιο. Η πρόταση έγινε αποδεκτή από τη Σχολική Εφορία και τέθηκε σε εφαρμογή από το επόμενο σχολικό έτος. Η μεταρρύθμιση αυτή των σχολείων της Μυτιλήνης, με εξαίρεση ίσως την αυτοτέλεια του δημοτικού σχολείου, δεν θα μεταβάλει ουσιαστικά τον προσανατολισμό και το πνεύμα του συστήματος. Παρά την ώθηση των θετικών επιστημών από το Μιχ. Στεφανίδη, δεν θα απομακρυνθεί ουσιαστικά από τον καθαρά παραδοσιακό, θεωρητικό προσανατολισμό του.
Ο Πέτρος Παπαγεωργίου θα παραιτηθεί για καθαρά προσωπικούς λόγους το 1899 και τη διεύθυνση του Γυμνασίου θα αναλάβει ο φιλόλογός Δ. Χ#Σπύρου για ένα χρόνο. Το 1900, με πρόταση του Λεσβίου καθηγητή του Πανεπιστημίου Αθηνών Νεοκλή Καζάζη, η Σχολική Εφορία θα προσλάβει για ένα χρόνο το φιλόλογο Σπύρο Μωραΐτη. Το Σπύρο Μωραΐτη θα αντικαταστήσει στη διεύθυνση του Γυμνασίου ο από το 1888 καθηγητής του ιδίου σχολείου διακεκριμένος Πλατωνιστής, Ιωάννης Ολύμπιος. Ο διορισμός του Ιωάννη Ολυμπίου θα ακουστεί με ενθουσιασμό και με μεγάλη ευχαρίστηση στη Μυτιλήνη. Δάσκαλοι, μαθητές, γονείς τον λάτρευαν, όχι μονάχα για την μεγάλη του επιστημονική μόρφωση, μα και για το σπάνιο ηθικό του ανάστημα. Ο Ολύμπιος θα παραιτηθεί το 1907 και θα ασχοληθεί με τη συγγραφή της Φιλοσοφίας του Πλάτωνα ως το 1910. Τον διαδέχθηκε ο Λέσβιος φιλόλογος Εμμανουήλ Δαυϊδ που παρέμεινε στη γυμνασιαρχία και μετά την απελευθέρωση της πατρίδος του, ως το 1914. Η διευθυντική και εκπαιδευτική θητεία του Εμμανουήλ Δαυίδ επαινείται ιδιαίτερα στην έκθεση του Νείλου Σακελλαρίου που δημοσιεύθηκε στο βιβλίο «Διάφοροι μελέται περί των νήσων».
Στα τελευταία χρόνια της τουρκοκρατούμενης Λέσβου τον εκπαιδευτικό κόσμο της Μυτιλήνης και ιδιαίτερα του Γυμνασίου θα τον απασχολήσει η διαμάχη που έχει ξεσπάσει για το γλωσσικό ζήτημα. Πέρα, όμως, από τη γλωσσική διαμάχη, ένα άλλο θέμα που θα απασχολήσει για πολλά χρόνια τους φορείς της εκπαίδευσης ήταν και η λειτουργία των Γαλλικών σχολών, αρρένων και θηλέων που θα ιδρυθούν το 1902. Στο πρόγραμμά τους περιλάμβαναν και εμπορικά μαθήματα. Παρά τις απόψεις ορισμένων Εφόρων που πρότειναν την εισαγωγή Εμπορικών μαθημάτων στο Γυμνάσιο, προκειμένου να μη θιγεί ο κλασικιστικός του χαρακτήρας, θα αποφασισθεί τελικά η ίδρυση της Εμπορικής σχολής, η οποία θα λειτουργεί παράλληλα με το Γυμνάσιο. Τελικά, η εμπορική σχολή θα ιδρυθεί πολύ αργότερα, το 1909, αλλά δεν θα λειτουργήσει λόγω έλλειψης πόρων και ειδικευμένου προσωπικού.
