Будинок споруджено спеціально для гімназії, яка раніше винаймала приміщення, за проектом та під наглядом штатного архітектора Київського навчального округу, військового інж.-полковника М. Чекмарьова. Підрядчик Л. Гінзбург. Місцем забудови обрали колишній Кінний майдан, де проводилися кінні ярмарки на «Новому Строєнії» у долині р. Либідь. Закладання відбулося 29 травня 1897, в липні 1898 гімназію переведено в цю споруду, опоряджувальні роботи тривали до 1899. Значні кошти на спорудження будинку, загальна вартість якого склала 155 тис. крб., зібрав колишній директор гімназії О. Михайлов та діючий директор М. Стороженко, залучалися також пожертви мешканців «Нового Строєнія» та окремих філантропів, серед яких найбільші внески зробили підприємці — брати Л. і Лаз. Бродські та Н. Терещенко, які пожертвували на будівництво по 3 тис. крб. кожний. Водночас протягом 1897—1902 на частині Кінного майдану поряд із гімназією було влаштовано новий сквер з невеликим фонтаном.
Планування будинку відзначалося чіткім розподілом функцій. На першому поверсі містилися парадний вестибуль, кабінет директора, інспекторська, класні кімнати, на другому — висока актова зала (виділена підвищенням даху), бібліотека, класні кімнати, фізкабінет, учительська, чайна, у підвалі - канцелярія, архів, квартири службовців, калориферна. У середньому крилі на першому поверсі — гардеробна, буфет, спортивна зала, на другому поверсі — гімназійна домова церква в ім'я св. Миколи. У кожному з бічних крил на обох поверхах було влаштовано по три навчальні приміщення (загалом 12), зблоковані навколо окремих рекреаційних зал (з них вісім навчальних, підготовче, два запасні та фізичний кабінет). Поряд з будинком стояв невеликий цегляний сарай.
1920 під час військових дій будівлю гімназії значно пошкоджено. 1929, після відновлення, тут розмістилася трудова школа. У повоєнний час будинок використовувався органами безпеки; на поч. 1990-х рр. — медичний заклад. Внутрішнє планування змінене. Двоповерховий, частково на цокольному напівповерсі, цегляний, тинькований, у плані Ш-подібний. Перекриття пласкі. Дах двосхилий, бляшаний. Центральний вхід з боку провулка. Зовнішній вигляд будівлі справляє враження ошатності й урочистості. Крім головного фасаду по пров. Горького, також ретельно декоровано у стилістиці ренесансу бічні фасади. Головний фасад симетричний (за винятком ухилу вздовж провулка), центральний ризаліт з парадним порталом оформлено портиком з двох подвійних коринфських колон та трикутним фронтоном. У тимпані фронтону в радянський час вміщено п'ятикутну зірку та символи праці. Фасад з боку вул.Червоноармійської асиметричний, розкріпований паладіанськими потрійними вікнами на другому поверсі. У декорі застосовано рустування й ланцюжки рустів, пілястри з коринфськими капітелями, різноманітні форми вікон; фриз і карниз прикрашені ліпленим орнаментом.
Будинок — цінний зразок громадської споруди у стилі історизм.
Четверта чоловіча гімназія існувала спочатку у вигляді училища, потім — прогімназії, статус гімназії заклад, що працював у найманих приміщеннях, набув 1883. Гімназія містилася в цьому будинку до 2-ї пол. 1914, коли її приміщення було передано під еваку-аційний лазарет для тяжко поранених солдатів. Заняття того року відбувалися в другу зміну у Восьмій Київській гімназії (сучасна пл. І. Франка, 5). Станом на 1915 у навчальному закладі працювало 34 особи, з яких викладачів — 25, на адміністративних посадах — 2, на навчально-допоміжних —3, службовців у канцелярії — 3, лікар — 1. У жовтні 1915 навчальний заклад евакуйовано в Саратов.
У цьому будинку гімназії працювали відомі діячі науки і культури.
До 1914 викладав історію Ківлицький Євген Олександрович (1861—1921) — історик, педагог, громадський діяч, бібліограф, бібліотекознавець, редактор журналу «Киевская старина» (1889— 93), фактично перший директор Всенародної бібліотеки України (1919—20). Працював у гімназії з 1891. Одночасно викладав у гімназії О. Дучинської, секретар Педагогічої ради в ній. Член Київського літературно-артистичного товариства, член правління Товариства сприяння народній освіті, що діяло при Народній аудиторії в Києві.
До 1906 викладав російську мову Левицький Орест Іванович (1849—1922) - історик, правознавець, археограф, етнограф, письменник, літературознавець, один із засновників і акад. УАН (з 1918), віце-президент УАН—ВУАН (1919—22), президент ВУАН (1922). Працював у гімназії з 1874. Одночасно — секретар Тимчасової комісії для розгляду давніх актів та створеної на її основі археографічної комісії УАН (1874—1921). Член Історичного товариства Нестора-літописця, Наукового товариства ім. Т. Шевченка у Львові, співробітничав у журналі «Киевская старина».
1895—1909 директором навчального закладу був Стороженко Микола Володимирович (1862—1942) — історик, педагог, громадський діяч. Одночасно з 1904 очолював Міністерську жіночу гімназію (до 1920), з 1909 — директор Першої Київської гімназії, гласний Київської міської думи (1902—12). Опікувався дітьми з незаможних родин, клопотав перед міською владою про призначення їм стипендій.
Був членом Київської Старої громади, Тимчасової комісії для розгляду давніх актів, Історичного товариства Йестора- літописця.
Учнями гімназії були відомі діячі культури.
1900—04 — Вертинський Олександр Миколайович (1889—1957) — співак, актор, поет і композитор. Навчався спочатку у Першій гімназії, де закінчив підготовчий клас. Важке дитинство без батьків спричинило складності у навчанні (виключений з п'ятого класу).
1909 – 12 — Івашкевич Ярослав (1894—1980) — майбутній класик польської літератури. Після гімназії закінчив Університет св. Володимира (1918) і виїхав з Києва. Тепер ім'я письменника носить одна з київських вулиць.
1910 – 19 — Кричевський Василь Васильович (1901—78) — живописець, художник кіно, випускник Київського художнього інституту (1923). Син архітектора і художника В. Кричевського. Емігрував, помер у США.
1908 - 17 — Кричевський Микола Васильович (1898—1961) — живописець художник театру, графік. Емігрував, помер у Парижі (Франція).
Тепер у будинку містяться державні установи [2000].