Высочайшим указом 8 декабря 1828 года Государь Император Николай I повелел открыть гимназию в каждом губернском городе.
Открытие гимназии в Томске состоялось 10 декабря 1838 года. Целью гимназии была подготовка государственных служащих и учителей школ.
Первым директором стал Иван Григорьевич Новотроицкий.
По первому набору в гимназию приняли 25 учеников, спустя 6 лет (1844) состоялся первый выпуск — 6 человек. Курс гимназии составлял 7 (с 1871 года — 8) лет. Зачисление проводилось по итогам вступительных экзаменов. Перевод в следующий класс также осуществлялся по итогам переводных экзаменов. Обучение было платным. При гимназии существовали стипендии — имени Императора Николая I, имени Б. И. Сциборского.
Первым зданием для гимназии служил бывший дом купчихи Е. Хлебниковой (современный адрес — проспект Ленина, 129 / Совпартшкольный переулок, 11 — объект культурного наследия № 7000165000). С 1885 года часть занятий проходила в здании Томского университета. В 1897 году по проекту томского архитектора Павла Нарановича было построено здание специально для гимназии.
В губернскую гимназию принимали только мальчиков. Когда в городе появилась женская (Мариинская) гимназия (1863), губернскую стали называть Томской мужской гимназией.
Программа обучения включала Закон Божий, русский язык, древние языки (латинский и, до 1901 года, греческий), историю, математику, физику, географию, космографию, логику, французский и немецкий языки, законоведение (которое преподавал член Томского окружного суда) и такой не совсем теперь понятный нам предмет — философскую пропедевтику. Собственная гимназическая библиотека насчитывала до 15 000 томов и являлась одной из лучших в городе. При гимназии была своя церковь.
Педагогический состав быстро менялся, часты были прошения учителей об освобождении от должности по причине ослабления их здоровья из-за суровости местного климата.
Одним из директоров гимназии был Иван Кузьмич Смирнов (?—1912) — отец учёного-археолога Я. И. Смирнова.