Здание женской гимназии помнит Керчь в разрезе нескольких эпох. Находится оно на улице Театральной, любители-путешественники рекомендуют его к обязательному посещению в программе прогулок по городу-герою. Оно не просто удивительно с точки зрения архитектурных исполнений, в этих стенах хранятся великие тайны разных времен.

После присоединения Крыма к России в 1783 году руководство города стало задумываться о повышении уровня грамотности населения, особое внимание уделяли перспективе женского образования. Впервые эта идее посетила Николая I: однажды он побывал в учебном заведении для женщин и решил реализовать нечто подобное в Керчи.

Первая общественная женская гимназия была открыта в городе в сентябре 1873 года. Сначала классами для занятий служили наемные помещения, лишь в 1885 году учениц перевели в главное здание на улице Дворянской. Его выстроили на месте дома, в котором некогда проходили важнейшие городские приемы и мероприятия, здесь, кстати, в свое побывали Пушкин и Раевский. Строить главное здание гимназии начали в 1883 году по проекту архитекторов Курускова и Красовского.

Очень быстро гимназия стала престижным учебным заведением южной России, во многом – благодаря талантливому педагогу Марии Хвостовой, которая много лет здесь работала.

Говорят, что в гимназии давали отличную образовательную базу юным девицам. В программе значились иностранные языки, история, математика, педагогика, география, чистописание и многие другие науки. Не забывали и о талантах воспитанниц: рукоделие, пение, танцы, рисование – эти и многие другие способности педагоги старались развить в своих ученицах. Не удивительно, что выпускницы гимназии с таким уровнем знаний легко устраивались в жизни. В то время в России было  не больше сотни гимназий, при этом лишь семь из них были исключительно женскими.

К началу XX века керченская женская гимназия уже пользовалась колоссальным успехом, сюда съезжались девушки с разных уголков страны, получить здесь образование считалось очень престижным. Руководство города приняло решение о расширении учебного заведения и строительстве дополнительных корпусов.

В годы Великой Отечественной войны здание сильно пострадало. Восстановить его удалось только в 1953 году. 

Несмотря на вехи истории, за годы существования здание женской гимназии не меняло предназначения: в этих стенах всегда давали образование, учили, воспитывали. Менялись лишь статус и название. В 1989 году учебному заведению вернули статус гимназии и присвоили имя В. Г. Короленко.