36 СОУ "Максим Горки" е наследник на първото училище в Красно село, открито през 1915 г. в къщата на Иван Шиндаров. От 1917 г. до 1952 г. училището носи името на генерал Иван Колев - пълководец и патриот, останал в славната военна история на България с участието си в битката при Кочмар, Северна Добруджа през 1916 г. По-късно със средствата на населението е построена сградата на улица "Пирински проход" № 35. Състояла се е от една монолитна постройка на два етажа. През бурните години на втората световна война учебният процес не е прекъсвал.
               Постепенно кварталът се разраства и през 1959 г. е построено ново крило, за да поеме големия брой ученици. Училището дава началото на две нови  училища в района.

                От 1952 г. до днес (повече от половин век) патрон на училището е руският писател Максим Горки - автор от световна величина, формирал литературните мирогледи на творци като Бърнард Шоу, Хърбърт Уелс, Стефан Цвайг и други. Пред сградата на училището има бюст-паметник на Максим Горки, който е единствен в България. Музейната сбирка, посветена на патрона, е събирана повече от 30 години.
                Със своята богата  история, училището е едно от най-старите в столицата. Доказало е с годините своето качество на обучение. Поколения възпитаници на 36 СОУ "Максим Горки"се развиват успешно във всички сфери на обществения живот, като достигат успехи не само за училището, но и за Република България.