1906-cı ildə Nikolay Pavloviç Stepanov Rostovda dörd sinifli kişi gimnaziyasını açır. İlk əvvəllər gimnaziya kimsəsizlər evində yerləşirdi. Ancaq bir necə il sonra Stepanov gimnaziya üçün yeni binanı timkəyi qərara alır. Gimnaziya üçün yeni bina 1915-ci ildə P. Y. Lyubimovun layihəsi əsasında inşa edilmişdir. Gimnaziyaya 14-15 yaşından gəbul həyata keçirilirdi. Hazırlıq sinfində il ərzində 100, birinci sinifdə isə 130 rubl pul alınırdı. 1916-cı ildən gimnaziyada həm oğlanlar həm də qızlar təhsil ala bilirdilər.

Rusiyada olan vətəndaş müharibəsi zamanı gimnaziya fəaliyyətini dayandırmamışdır. Sovet hakimiyyəti dönəmində gimnaziya № 95 əmək məktəbinə çevrilir. 1926 ildən Troski adına № 5 yeddi illik məktəb adlanır. 1928-ci ildən №10 doqquz illik məktəbə çevrilir. 1938-ci ildən isə bina M. Qorki adına №36 orta məktəbi adlanır. 1962-ci ildən bir sıra fənlər ingilis dilində tədris olunmağa başlanılır. 1997-ci ildən isə məktəb № 36 gimnaziya adlanır.

2007-ci ildə gimnaziya «Rusiyanın ən yaxşı məktəbi» adlı ümumrudiya yarışmasında iştirak etmişdir.

Gimnaziya binası üç mərtəbədən və zirzəmidən ibarətdir. Fasadı kərpiç bəzəklərlə işlənmişdir. Bina modern stilinə sahibdir. Bina Qorki küçəsi və Sobornı xiyabanının küncündə yerləşir.

Aleksandr Lvoviç Minç — alim-radiotexnik, 1908—16-cı illərdə gimnaziyada təhsil almışdır. Bununla əlaqədar 1977-ci ildə binanın fasadına memorial lövhə vurulmuşdur.

A. Bentqulin — jurnalist, publisist, yazıçı.