Кінатэатр "Перамога" адносіцца да ліку першых, пабудаваных у Мінску пасля Вялікай Айчыннай вайны. Пад кінатэатр было вырашана рэканструявацъ каробку клуба харчавікоў імя Сталіна. Клуб быў узведзены ў 1929 г. па праекце архітэктара А. Бурава. У Вялікую Айчынную вайну будынак быў пашкоджаны.
Праектныя работы распачаліся ў пачатку 1946 г. у "Белдзяржпраекце" пад кіраўніцтвам Палкоўнікава. Варыянт праекта Палкоўнікава не быў прыняты. У 1947 г. распачаўся другі этап праектаванння ўжо пад кіраўніцтвам I. Лангбарда. Ён у пэўнай ступені скарэктаваў праектнае рашэнне Палкоўнікава, найперш план будынка. I. Лангбард значна скараціў на галоўным фасадзе бакавыя крылы. Правы рызаліт да таго ж быў зменшаны па шырыні. Такім чынам, галоўны фасад асноўнага аб’ёму і фасадныя сцены правага рызаліта праектаваліся новыя. Праектнае задание, распрацаванае І.Лангбардам, было зацверджана Архітэктурным саветам Упраўлення па справах архітэктуры пры СМ БССР 16.11.1947 г. На яго аснаванні ў 1948 г. былі распрацаваны тэхнічны і рабочы праекты рэканструкцыі былога клуба ў кінатэатр "Перамога". На гэтым этапе праектавання разам з I. Лангбардам прынялі ўдзел архітэктар М. Бакланаў і інжынер-канструктар Арлоў. У аснову было пакладзена папярэдняе праектнае рашэнне I. Лангбарда з некаторымі дапрацоўкамі па ўнутранай перапланіроўцы і архітэктурным рашэнні фасадаў.
Кінатэатр "Перамога”ў адпаведнасці з праектам быў пабудаваны ў 1947- 1949 гг. Будынак характарызаваўся як аднапавярховы за выключэннем двухпавярховага цэнтральнага аб'ёму. Пад кінатэатр былі рэканструяваны часткі наружных і ўнутраных сцен былога клуба, узведзены новыя сцены на новых падмурках. Старыя падмуркі ўмацаваны падводкай новых. Міжпаверхавыя перакрыцці ўзведзены новыя. Маецца фотаздымак 1951 г., на якім зафіксаваны новы кінатэатр адразу пасля будаўніцтва з боку вул. Камсамольскай.
Кінатэатр пачаў функцыянавацъ у лістападзе 1950 г.
У 1986-89 гг. праведзены капітальны рамонт кінатэатра з заменай пакрыцця даху.
Работы па рэканструкцыі кінатэатра “Перамога” пачаліся ў 2022 годзе. Вонкава будынак амаль не змяніўся. Былі ўзмоцнены падмуркі і сцены, зроблены новы дах і поўная перапланіроўка памяшканняў, адноўлены элементы дэкору. Інтэр'еры вытрыманы ў стылістыцы 50-х гадоў. У фае адкрылася тэматычная выстава і фотазона, прысвечаная гісторыі кіно, на другім паверсе разгарнулася экспазіцыя на тэму гісторыі горада.
У звычайным рэжыме кінатэатр павінен пачаць сваю працу ў жніўні.
