Мысль об основании в Керчи гимназии впервые была высказана императором Николаем I при посещении девичьего института в 1837 году. Керченское городское управление, осознавая важность женского образования в деле умственного и нравственного развития населения, признало нужным учредить в городе и женскую гимназию.
14 сентября 1873 года последовало открытие городской общественной женской гимназии. Первое десятилетие своего существования гимназия ютилась в наемных помещениях, а с 1885 года перешла в прекрасное здание на Дворянской улице. Благодаря симпатиям Керченского общества к своему детищу и большим педагогическим талантам начальницы гимназии Марии Кирилловны Хвостовой, женская гимназия являлась весьма солидным учебным заведением на юге России. После революции здание было отдано под школу.

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

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

с 1836 года в институт принимали девиц дворянского и купеческого происхождения. В 1837 году девичий институт посетил император России Николай 1 и посоветовал основать в Керчи женскую гимназию. Поскольку образование стало все более и более востребованным и учиться в Керчь приезжало все больше благородных девиц, Керченское городское управление признало необходимость в строительстве нового здания для женской гимназии.

В Керченской гимназии девушки получали великолепное образование по меркам того времени, за несколько учебных лет изучались иностранные языки, педагогика, математика, география, чистописание, история, рисование, русский язык, рукоделие, пение, гимнастику и многое другое. Такой уровень образования был очень высок и востребован, ведь во всей России на конец 19 века насчитывалось 98 гимназий и только 7 из них были женскими.
В 1881 году городские власти решили разрешить строительство нового здания для женской гимназии на улице Театральной (бывш. Дворянской). Кстати, ранее во дворе будущей гимназии находился генералитетский дом, где принимали высоких гостей города. В частности, там останавливался Пушкин и Раевский во время своих путешествий по Крыму.

В 1883 году был заложен первый камень, свидетельствующий о начале строительства гимназии. В качестве архитекторов были приглашены Курусков и Красовский. Молодые таланты приехали из крупного российского града, где также строили по своим проектам доходные дома, отели питера. Построена женская гимназия была за 2 года и в 1885 ее торжественно освятили.
Дальнейшее содержание здание, как и его строительство финансировалось из городского бюджета. Условия для обучения в новом здании были блестящими, здесь была своя библиотека, просторные классы, беседка для отдыха. Керченская гимназия стала такой популярной, что в начале 20 века было принято решение о том, чтобы достроить дополнительные учебные помещения. В 1905-1909 гг была выстроена южная часть гимназии с башней. Архитектором этой пристройки стал уже Лагорио, который тогда работал главным архитектором Керчи.

Женская гимназия за все время своего существования не меняла основного профиля, даже в советское время здесь располагалась школа. По сей день в стенах гимназии звонко звучит детский смех и раздаются мерные звуки преподавательских голосов: гимназия стала школой №3 и была названа именем Короленко — известного русского писателя и общественного деятеля.
Только в 1989 году власти вернули зданию первоначальный статус гимназии.