Приехав в 1868 году с мужем А. В. Оболенским в Петербург из Ковно, Александра Алексеевна Оболенская вошла в кружок образованных женщин (А. П. Философова, М. А. Быкова, Е. О. Лихачёва, М. В. Трубникова), в котором горячо обсуждался вопрос об открытии Высших женских курсов в Петербурге. Александра Алексеевна, будучи недовольной тем, как обстоит дело со средним образованием для девочек, решила открыть школу, обучение в которой готовило бы к университетскому курсу.
Гимназия была открыта в ноябре 1870 года и считалась одной из лучших женских гимназций. Имела права правительственной гимназии, была обязана подчиняться правилам, программам и распоряжения Министерства народного просвещения и Петербургского учебного округа. Имела семь классов и дополнительный восьмой - педагогический. Плата составляла от 100 до 200 рублей в год. Число учениц колебалось от 100 до 200.
С 1871 года гимназия размещалась в доме № 16 по Средней Першпективе (ныне ул. Маяковского). В 1901 году гимназия переезжает в специально построенный дом № 8 по Баскову переулку (архитектор Г. В. Барановский, 1899—1900). В 1902—1903 годах здание было расширено под руководством военного инженера Г. Л. Кононова.
После смерти своей создательницы и первой владелицы кн. А. А. Оболенской гимназия не изменила своего названия. Оболенской наследовала ее дочь, кн. Мария Андреевна Мещерская (урожд. Оболенская), на здании гимназии появился герб Мещерских, но это не помешало гимназии до конца сохранить свое название.
После революции и переименования гимназии в 16-ую единую трудовую школу в ней продолжали работать учителя дореволюционного набора. Шестнадцатой единой трудовой, а позднее средней школой до 1930 года заведовал бывший учитель гимназии кн. Оболенской Даниил Александрович Александров, отец математика, академика А. Д. Александрова.