В группе знакомых между собой предпринимателей возникла мысль о создании собственной частной школы, которая бы отличалась от государственных учреждений более гибкой программой. Эти планы были близки их общему другу педагогу Карлу Иоганну (в русской традиции Ивановичу) Маю, ему и предложили возглавить новое учебное заведение.
10 сентября 1856 г. при ближайшем содействии своих немецких друзей К.Май открыл маленькую частную школу в своем доме на 1-й линии (в надворном флигеле д. 60).
Сначала учеников было только 10 человек, родители которых были хорошо знакомы К.Маю. Отчасти благодаря этому с первых дней в школе воцарилась уютная, почти семейная атмосфера, наполненная постоянной заботой и вниманием к каждому ученику.
Гимназия была частной, и за обучение взималась плата — 160 руб. в год. С самого начала при школе были организованы пансион, где ученики находились круглосуточно, и полупансион – с ночлегом в домашних условиях. При содержании в пансионе годовая плата составляла 600 руб. В начале 20 в. вследствие инфляции она была немного увеличена.
Учебный день начинался в 9 часов утра и продолжался до 16 часов, а по средам и субботам – с 8 до 12 часов. Для изучения древних языков вводился дополнительный час – с 8 до 9 утра. Урок продолжался 53 минуты, перемена – 7 минут. Большая перемена, с 12 до 13 часов, отводилась для завтрака и гимнастических упражнений. Ежедневно по полчаса ученики занимались на гимнастических снарядах, развлекались различными подвижными играми или маршировали по двору. К.И. почти всегда присутствовал на маршировках и усердно командовал: "Аз, два, аз, два".
Оценка знаний учеников производилась по пятибалльной системе, причем в цензурах (четвертях) выставлялись усредненные баллы с точностью до сотых. По каждому предмету оценивались отдельно успехи и прилежание. Такая система приводила иногда к курьезным случаям. Однажды Дмитрий Семенов, имевший блестящие математические способности, получил в цезуре по геометрии в 6 классе единицу за прилежание и пять за успехи. Ученик оценку конечно же оспорил, сказав: “Если я знаю отлично, по вашей же оценке, хотя бы и ничего не делая, то зачем же мне делать больше, все равно я лучше чем отлично знать не буду”. Однако оценку ему не исправили.
Из класса в класс ученики переводились на основании среднегодовых оценок по всем предметам, каждая из которых должна была быть не ниже трех. Были и переводные экзаамены, которые проводились прямо во время уроков в конце года. На эти уроки приходил сам Май и вместе с учителем проводил опрос по всей программе. Таким образом уточнялась годовая оценка. Неуспевающие получали задания на летние каникулы, выполнение которых проверялось перед началом учебного года.
В 1882 г. гимназии Мая были присвоены права, предоставленные гимназиям Министерства народного просвещения. С тех пор школа стала называться "Гимназия и реальное училище К.И.Мая",
Почти на всем протяжении истории школы Мая преподавание в ней велось на двух языках: русском и немецком. На немецком языке велись уроки немецкого языка, древних языков, всеобщей истории, алгебры и геометрии. Все годы с момента основания школы К.И.Май был ее директором.
