Будынак кінатэатра «Перамога» ў Мінску размяшчаецца на месцы, дзе стаяў клуб харчавікоў, пабудаваны ў 1929 годзе, згодна з праектам, архітэктарам якога з'яўляўся А. Бураў. Амаль чатыры стагоддзі таму на месцы забаўляльнай установы размяшчаўся касцёл, які ў 1633 годзе з'яўляўся складнай часткай каталіцкага жаночага манастыра. Каталіцкі манастыр праіснаваў больш за дзвесце гадоў, і ў 1872 годзе яго месца заняў Спаса-Праабражэнскі жаночы манастыр. Вуліца была перайменаваная ў Праабражэнскую, а сам будынак заняў дзве вуліцы і формай нагадваў літару «П».

З прыходам новай улады і да Вялікай айчыннай вайны памяшканне займаў клуб імя Сталіна. У клубе было дазволена праводзіць урачыстыя мерапрыемствы, ладзіліся выставы. У 1935 годзе адміністрацыя клуба арганізавала першую выставу дзіцячых цацак, якая мела ўсебеларускі маштаб. Мясцовыя вытворцы прадставілі на ёй больш за 150 тысяч экспанатаў.

Падчас вайны немцы арганізавалі ў будынку клуб для сваіх салдат, які быў узарваны падпольшчыкамі ў 1943 годзе.

Пасля вайны было прынята рашэнне аб аднаўленні будынка. Па сутнасці, яго прыйшлося падымаць з руін. Праца пачалася ў 1949 годзе, і праз год кінатэатр расчыніў дзверы для першых наведвальнікаў.

Будынак па вуліцы Інтэрнацыянальнай, 20 адносіцца да помнікаў архітэктуры пасляваеннага перыяду. Архітэктары Іосіф Лангбард і Міхаіл Бакланаў спраектавалі першы кінатэатр беларускай сталіцы ў стылі так званага сталінскага ампіру.

Цэнтральны партал будынка кінатэатра «Перамога» мае дзве карынфскія калоны. Перыметр будынка акружае магутны карніз. Пазней на фасадзе кінатэатра з'явіліся паўкруглыя фрэскі.

Кінатэатр «Перамога» быў першым сярод іншых кінатэатраў Беларусі, у якіх з'явіўся шырокі экран. Памяшканне складалася з трох залаў, максімальна ўмяшчаючы ў сябе больш за паўтары тысячы гледачоў. Увазе наведвальнікаў, якія засталі кінатэатр у першапачатковым праекце будынка, прапаноўвалася памяшканне для прагляду дакументальных фільмаў. Маглі яны быць здзіўлены і відамі летняга адкрытага кіназала, разлічанага на 610 месцаў, адкрытых для наведвальнікаў з мая па лістапад. Побач з ім меўся фантан і скульптуры жаб па крузе.

Новая эпоха адзначылася ўключэннем будынка кінатэатра «Перамога» ў Дзяржаўны спіс гісторыка-культурных каштоўнасцяў Рэспублікі Беларусь і пачаткам распрацоўкі плана яго рэстаўрацыі.

У 2014 годзе будынак кінатэатра зведаў рэканструкцыю. Архітэктары стараліся максімальна захаваць самабытнасць інтэр'еру, якая прысутнічала ў першапачатковым праекце. Фасад будынка быў дапоўнены толькі пандусам і невялікай пад'ёмнай пляцоўкай для інвалідных калясак.

У нашы дні кінатэатр «Перамога» можа размясціць 488 гледачоў, мае найноўшую сістэму аб'ёмнага гучання. Доўгі час кінатэатр з'яўляўся адзіным у Беларусі членам асацыяцыі Europa Cinemas, куды ўваходзіць 469 кінатэатраў з больш чым паўсотні краін.

Будынак кінатэатра «Перамога» ў Мінску з'яўляецца не толькі месцам сучаснага культурнага адпачынку жыхароў сталіцы і яе гасцей, але і славутасцю, якая ўключана ў многія турыстычныя маршруты.