В 1902 и 1904 гг. с тыльной стороны главного корпуса были пристроены помещения, в которых расположились классы, но возможности дальнейшего расширения гимназии уже почти исчерпались. Поэтому, а также учитывая введение в России всеобщего обучения, Евпаторийская дума приняла решение о необходимости строительства нового современного учебного здания. Для него было выделено одно из самых лучших городских мест — Шакаевский сад (ныне парк им. Ленина). Само сооружение предполагалось возвести в центре прямоугольного квартала, в промежутке между улицами Дувановской — Белинского-Александровской (теперь Пионерской) и Новой (ныне Бр. Буслаевых). По проекту здание было ориентировано центральным входом к театру и тогда еще строящейся библиотеке им. Александра II (сейчас им. А.С. Пушкина). Сметная стоимость объекта — 210—240 тыс. руб., не считая цены выделенного участка, которая, как минимум, равнялась 100 тыс. руб. Для финансирования столь дорогостоящих работ необходимо было привлечь весь имеющийся капитал города в сумме 35 тыс. руб., употребить третью часть суммы, вырученной от продажи дачных участков, приблизительно около 110 тыс. руб., а также обратиться в учебное ведомство с ходатайством о пособии в 100 тыс. руб. или хотя бы о беспошлинной ссуде. Городской голова А.И. Нейман, находясь по делам города в столице, лично обращался к министру народного просвещения и получил от него согласие на выделение требуемой беспроцентной ссуды в течение двух последующих лет — по 50 тыс. руб. ежегодно с условием, что ее город будет погашать из арендных денег за здание, причитающихся от министерства.
Проект учебного дома подготовил все тот же городской архитектор А.Л. Генрих в свойственном ему темпе — в кратчайший срок. Он был рассмотрен частным совещанием гласных думы 31 мая 1912 г. Предполагаемая к постройке гимназия насчитывала три этажа с подвалом, актовым залом (он же и гимназический зал). На первом этаже планировалось разместить канцелярию, архив, приемную, кабинет и квартиру директора, приемную для родителей, столовую. На втором — семь классов для младшего возраста и обширный рисовальный класс; на верхнем — столько же классов для старшеклассников, библиотеку, физические и естественные кабинеты с общей аудиторией. Учебные комнаты были рассчитаны на 40 человек, площадью около 16 кв. саженей каждая. Кроме того, в отдельно стоящем флигеле должны были разместиться квартиры по 3 комнаты каждая для помощников классных наставников и делопроизводителя. В качестве образца такого роскошного здания была выбрана одна из лучших на юге России — Пятая Одесская гимназия.
В следующем, 1913, году Министерство народного просвещения предложило изменить условия строительства нового гимназического здания, с чем согласилась Городская дума. Этот грандиозный проект не был воплощен в жизнь из-за вспыхнувшей Первой мировой войны.
Поскольку планируемое строительство могло начаться только в конце 1915 г., для улучшения условий обучения учащихся местное самоуправление решило осуществить пристройки, хотя это и было весьма обременительно для города. Так, четыре дополнительных классных комнаты появились у восточного крыла гимназии и два помещения — с противоположной стороны. Западней соорудили гимназический зал в два света с кабинетом врача и выполнили другие, более мелкие работы. Их завершили к 20 августа 1913 г., и полная сметная стоимость составила 50 тыс. руб. Таким образом, стоимость всех строений гимназии почти удвоилась и превысила более 100 тыс. руб. При этом город продолжал нести расходы на содержание гимназии в 10 тыс. руб. в год, в то время как арендная плата для министерства равнялась 4 тыс. руб.
Такое пристальное внимание Евпаторийской думы к народному образованию, желание нести затраты на содержание гимназии и улучшение условий ее функционирования способствовали постоянному повышению статуса учебного заведения, а следовательно, увеличению числа обучающихся в нем. Так, менее чем за 20 лет четырехклассная прогимназия была преобразована в шестиклассную (1900 г.), а в 1903 г. — в восьмиклассный состав. В 1914 г. она состояла уже из 8 основных и 4 параллельных классов. Соответствующим образом росло и число обучающихся в ней: в конце XIX в. — 74, в 1900 г. — 96, 1901 г. — 114, 1902 г. — 136, 1903 г. — 153, 1914 г. — 399 человек.