Следующим зданием за прогимназией — здание женской гимназии, бывшее Неплюевcкое училище, приобретенное городом, как мы указали выше.

История гимназии, как и большинства учебных заведений города Оренбурга, связана с именем Н. А. Крыжановского; он поднял этот вопрос еще в 1865 г. генерал губернатор, указывая, что существовавшее в городе Оренбурге училище 2-го разряда (ныне прогимназия) не удовлетворяет многих граждан «незначительностью программы», прием же в Николаевский институт ограничен по числу ваканций, а потому, по мнению губернатора, необходимо открытие училища 1 разряда с пансионом, вследствие местных условии, как например «частыя более или менее продолжительныя командировки в степь и проистекающия при этом затруднения для семейного человека при оставлении на это время детей, посещающих училище». Генерал-губернатор предложил гражданскому губернатору обратиться за содействием к предводителю дворянства и к городскому обществу, дабы они постановили приговоры об ассигновании на содержание училища 1 разряда определенных сумм; с своей стороны Н. А. Крыжановский предполагал обратить на этот предмет имевшиеся в его распоряжении остатки денежных сумм.

8 января 1866 года дворянское собрание единогласно постановило: назначить на предполагаемое к открытию женское училище 1 разряда единовременный денежный сбор по одной копейке с каждых десяти десятин, сделав его обязательным для всех помещиков и землевладельцев Оренбургской губернии.

Но впоследствии оказалось, что журнал собрания был редактирован неправильно и благодаря такому обороту дела пожертвование дворян Оренбургской губернии выразилось цифрою в 70 рублей, да и те поступили не скоро и не без затруднений.

Оренбургское городское общество 6 апреля 1866 года вместо того, чтобы обсуждать вопрос об открытии нового училища, постановило преобразовать существующее училище 2 разряда, сделав его училищем 1 разряда, причем общество пожертвовало 10 тыс. руб. — содержание, которое получало училище 2 разряда, дало обязательство на постройку со временем дома и желало, чтобы училище носило название «Александровское», при этом училище должно было быть главным образом для детей купцов и мещан.

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

1) испросил разрешение употребить на гимназию оставшиеся после училища лесоводства и земледелия 16.627 р. 71 к.;

2) собранные урядником Лосевым пожертвования в сумме 6.868 р. 73 к.;

3) отделить из 80 тыс. руб., собранных среди киргиз на открытие мужской гимназии 25 тыс. руб.

4) наконец, город изъявил желание пожертвовать 10 тыс. руб. и ежегодно отчислять из прибылей общественного банка по 3 тыс. руб.

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

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

Министр изъявил свое согласие на открытие училища, но предложил генерал-губернатору снестись с попечителем учебного округа. Однако, Крыжановский пренебрег этой формальностью — он вообще любил сноситься непосредственно с высшим начальством, игнорируя посредственные звенья.

Торжественное открытие училища состоялось лишь 3 декабря 1868 года, хотя занятия начались с осени. Первое время училище помещалось в частном доме Худояр Хана — на Водяной улице.

Затем гимназия перешла в городское здание, которое после пожара 1879 года было отремонтировано за счет города.