20 сентября 1873 года в Москве появилось женское учебное заведение, целью которого было поставлено «дать воспитанницам вполне законченное среднее образование». Первоначально были открыты три низших класса; за основу была принята программа в объёме курса мужских гимназий, кроме древних языков. Классы расположились в помещении при доме Демидова, затем — Козловской, потом — на Поварской улице. В 1873 году начали обучение 15 воспитанниц, в следующем году поступило 19 воспитанниц, и к 1880 году число обучавшихся достигло 142 человек; к 1884 году число воспитанниц снизилось до 84, однако в 1899 году их было 226. Первый выпуск, состоявшийся в 1881 году, состоял из 4 учащихся, окончивших 8 классов: Бобынина, Евецкая, Королёва и Мечникова. До 1889 года выпускницы для получения звания домашней учительницы должны были сдавать экзамен в испытательном комитете при московском университете — всего таких выпускниц было 78. В 1889 году учебное заведение было преобразовано в гимназию, которая располагалась на Пречистенке (д. № 17/9). В районе Пречистенки было две гимназии: Арсеньевская и Поливановская. «Связь между этими школами была самая тесная; если сыновья учились у Поливанова, дочерей отдавали к Арсеньевой. Преподавание было в большинстве случаев общее, почти все учащиеся знали друг друга, и, начиная с 6-го класса, между ними возникали юношеские романы.» — Аксакова Т. А. Семейная хроника Гимназия Арсеньевой давала право своим выпускницам на преподавание иностранных языков.