1530 wird im Rat der Stadt der Antrag gestellt, eine neue städtische Lateinschule zu gründen. Es gab bereits solche höheren Schulen, eine am Dom, die in erster Linie dazu dienten, den geistlichen Nachwuchs auszubilden, und für die Kinder des Bürgertums – ebenfalls am Dom – eine schola exterior und eine weitere solche an St. Jacobi, die aber beide dem kirchlichen scholasticus unterstanden.
Als rein städtische Schulen dagegen gab es Anfang des 14. Jahrhunderts an den Kirchspielen St. Marien, St. Petri, St. Ägidien und St. Klemens je eine der „dudeschen Scryfscolen“, die sich freilich auf Elementarunterricht beschränkten. Im Zuge der Reformation nahmen die Bürger auch die höhere Bildung selbst in die Hand: „Vor de ioget möte wy hebben eine gude Schole, dar der borger kindere beter ynne geleret werden wen bet to her.“ (Erster Satz der Kirchenordnung von 1531) Das Emanzipationsstreben des aufsteigenden Standes zeigt sich hier ebenso wie der zunehmende Bedarf an gebildeten Funktionsträgern in einer sich differenzierenden Gesellschaft.
Der Rat schickt eine Delegation nach Wittenberg. Luther selbst war unabkömmlich und betraut deshalb Johannes Bugenhagen mit der Aufgabe, der Stadt eine neue Kirchen- und Schulordnung zu geben. Bugenhagen hatte dies bereits in und für Braunschweig und Hamburg getan.
Als Ort für die neue Schule wird das Katharinenkloster ausgewählt: Es liegt zentral und bietet viel Platz für die 5 Klassen, verschiedene Funktionsräume und die Wohnungen der „Scholegesellen“ (Rector, Subrector, Cantor und 4 Pedagogi). Unterrichtsräume, Lehrerwohnungen und eine Bücherei werden eingerichtet. Finanziert wird die Schule aus Mitteln des Klosters, Zuschüssen der Kirche und der Stadt, dem Schulgeld (2 bis 4 Schilling) und den Einnahmen der Sängerschule: 1462 hatten Bürger eine ewige Messe gestiftet, deren Erträge u.a. in eine Sängerschule in der Hundestraße flossen. Diese war 1528 dem Katharineum angegliedert worden, die Schule übernimmt die Verpflichtung zum Chorgesang in den Kirchen und kann über die dadurch einkommenden Gelder verfügen.
Schon im März 1531 nahm das Gymnasium unter seinem ersten Schulleiter Hermann Bonnus die Arbeit auf: In den 5 Klassen wird vor allem Latein als die damalige internationale Wissenschafts- und Verwaltungssprache unterrichtet, von den grammatischen Grundelementen bis zum Verfassen lateinischer Gedichte und der Aufführung altrömischer Komödien. Auch die Anfänge des Griechischen, der Sprache des Neuen Testaments, werden unterrichtet. Vom Hebräischen werden nur Buchstabenkenntnisse verlangt, ferner Grundkenntnisse im Rechnen. Der Sonnabend ist dem Religionsunterricht gewidmet. Täglich mehrmals werden gemeinsame Gottesdienste abgehalten und der Chorgesang geübt. Neben dem Schulunterricht unterhält das reformierte Katharineum auch ein sogenanntes lectorium, in dem für interessierte Bürger lateinische Vorträge über theologische Themen gehalten werden, und später eine öffentliche Bibliothek.