Возведенное в 1939–1940 гг. здание изначально предназначалось для детей белорусской партийной номенклатуры.
Во второй половине 1930-х шел поиск новых архитектурных форм. Часть зодчих развивала, в соответствии с политическим заказом, так называемый «тоталитарный» стиль. А другая часть экспериментировала с элементами классицизма или неоклассицизма. В духе второго направления и была построена школа № 4, спроектированная главным архитектором Минска Герасимом Якушко. В 1979 году к зданию со стороны улицы Кирова пристроили новое 6-этажное крыло. Любопытно, что до постройки школы на этом месте стоял дом героя Русско-Турецкой войны 1877–1878 гг. генерала Михаила Скобелева, в чью честь до революции нынешняя улица Красноармейская называлась Скобелевской.