Основана Херсонская Мариинско-Александровская женская гимназия в 1854 году сестрами Гозадиновыми. Известные деятельницы народного просвещения Софья, Мария и Елена походили из дворянской семьи, которых Крымская война вынудила переселиться из Симферополя в Херсон в 1854 году. Из-за нехватки учебных заведения для женщин, сестрам Гозадиновым поступило предложение от директора училищ Херсона Захара Васильевича Коленко основать пенсион для благородных девиц.
В мае следующего года 40 воспитанниц пансиона начали обучение по программе уездного училища (2-го разряда) в арендованном доме Бухтеевой по улице Богородицкой.
Рассчитанный на шесть лет обучения курс состоял из одного подготовительного и трех основных классов. Подготовительный и первый основной класс были с двухлетними курсами.
Преобразование пансиона в частную гимназию произошло в 1864 году, а по прошествии трех лет получен статус общественной.
В 1868 году возведено здание гимназии на месте бывших казарм жандармского дивизиона на частные пожертвование горожан, при строительстве принимали деятельное участие городской голова А. И. Волохин и супруга вице-губернатора А. И. Корнович.
После чего опеку над гимназией взял на себя Попечительский совет. В 1885 году женская гимназия решением министерства народного просвещения в честь имени императрицы Марии Александровны получила наименование Мариинско-Александровской и восстановлен педагогический восьмой класс. Что и явилось основным стимулом Херсонского губернского правления при строительстве нового здания, соответствующего имени императрицы. В 1902 году 25 августа по проекту инженера Казимира Квинта закончено строительство нового комплекса гимназии.
Эклектичная архитектура здания привлекала внимание кровлей с тремя четырехгранными фигурами куполов над ризалитами.
Несмотря на то, что количество женских учебных заведений увеличивалось, получить в гимназии Гозадиновых образование считалось престижным и к 1900 году обучалось более 600 девушек.
В новом здании на учительские кафедры гимназии основанной сестрами Гозадиновыми взошли Елена и Софья. Мария Игнатьевна умерла в 1898 году. Будучи в преклонном возрасте и утомленные многолетним трудом, сестры с сожалением покинули гимназию в 1901 году, не дождавшись 50-летия основанного ими учебного заведения.
В 1906 году умирает Софья Игнатьевна. Елена — младшая из сестер унаследует все наследство сестер. в 1912–1913 годы Елена Игнатьевна не имея прямых наследников на свои средства вблизи Соляного спуска строит школу. На территории морского колледжа рыбной промышленности находится здание сохранившееся и поныне.
В голодном 1920 году не стало Елены Игнатьевны.
Здание гимназии после 1917 года использовали под казарму 45-го стрелкового полка 17-й Сивашской дивизии. В марте 1944 года, принадлежавшее военному оккупационному ведомству здание было взорвано немцами.