У 1969 - 1991 гг. архіў-музей месціўся ў будынку Царквы Святых Апосталаў Пятра і Паўла (сучасная вул. Ракаўская, 4) - адным з найстаражытнейшых помнікаў архітэктуры ў Мінску, пабудаваным у 1611 - 1613 гг.
Архітэктура храма не паддаецца адназначнай класіфікацыі, аднак цэлы шэраг асаблівасцяў не толькі дазваляе меркаваць пра яго нацыянальны беларускі характар, але і збліжае Петрапаўлаўскую царкву з іншымі крыху больш познімі культавымі збудаваннямі Мінска, створанымі ў стылі барока.
Хутчэй за ўсё, Петрапаўлаўская царква належыць да ліку збудаванняў, якія развіваюць традыцыі каменнай беларускай архітэктуры - гэта манументальныя, простыя па кампазіцыі, лаканічныя па дэкоры, аднанефныя, значна радзей - трохнефныя будынкі.
На Беларусі ў розныя перыяды існавалі "абарончыя храмы", альбо "храмы-крэпасці". Некаторыя даследчыкі дапускаюць, што Петрапаўлаўская царква з'яўляецца адной з найпазнейшых мадыфікацый храмаў гэтага тыпу. У аснову аб'ёмна-прасторавай і планіровачнай кампазіцыі царквы пакладзены прынцып сіметрыі: яго ўнутраная прастора з дапамогаю шасці масіўных слупоў падзелена на тры часткі, сярэдняя з якіх вышэйшая і шырэйшая за бакавыя і заканчваецца на ўсходзе гранёнай апсідай. Галоўны заходні фасад прадстаўлены дзвюма квадратнымі вежамі. Правая вежа трох'ярусная, левая - двух'ярусная. Абедзве аздобленыя арачнымі праёмамі і нішамі.
Стварэнне каменнага храма і манастыра на гэтым месцы было ініцыявана ў пачатку XVII ст. мінскай праваслаўнай талакой, якая сабрала адпаведную колькасць грошай. Пад пабудову храма і манастыра князёўнай Аўдоццяй Рыгораўнай Друцкай-Горскай у 1611 г. быў выдзелены лапік зямлі недалёка ад Свіслачы. У наступным, 1612 годзе мінчане пачалі на гэтым месцы будаўніцтва манастыра і саборнай царквы.
Пабудова храма вялася на ахвяраванні і з дапамогаю мінскіх праваслаўных жыхароў. У 1613 г. манастырскі храм быў у асноўным дабудаваны і асвечаны ў гонар апосталаў Пятра і Паўла. Тады ж тут пасяліліся манахі, якія прыехалі з Вільні, і пачаліся штодзённыя багаслужэнні. Праз чатыры гады пры манастыры ўжо істнавала праваслаўная школа. Каталіцкія святары спрабавалі зачыніць царкву і манастыр, а будынак перадаць уніяцкім святарам. Аднак, нягледзячы на гэта, манастыр набываў усё больш ўплыў: у 1613 г. сам польскі кароль Уладзіслаў IV падараваў яму прывілегіі. Рэлігійныя войны, што бушавалі ў сярэднія вякі ў Еўропе, часам прыводзілі вернікаў да жорсткіх сутыкненняў. Яшчэ ў 1617 г., пасля адкрыцця ў Мінску Петрапаўлаўскай царкоўнай школы, уніяцкія святары ўчынілі збіццё вучняў. Праз два гады натоўп фанатычных уніятаў вырашыў разграміць манастыр. Манахі і мясцовыя жыхары, якія прыйшлі ім на дапамогу, тры дні адбіваліся ад раз'юшанага натоўпу. У 1734 г. грамада польскіх шляхціцаў зладзіла ў царкве пагром. Пасля гэтага манастыр прыйшоў у заняпад. У канцы 1780-х - пачатку 1790-х гг. у ім жылі толькі пяцёра манахаў, дый праваслаўных заставалася ў Мінску няшмат. Гараджане прытрымліваліся пераважна каталіцкай і ўніяцкай веры.
У 1793 г. Мінск быў далучаны да Расіі. Расійскія ўлады скасавалі Петрапаўлаўскі мужчынскі манастыр, а царкву рэканструявалі. Перабудовай царквы кіраваў першы губернскі архітэктар Фёдар Крамер.
У 1795 г. царкве надалі статус кафедральнага сабора Менскай епархіі і перайменавалі ў Кацярынінскі сабор у гонар пакутніцы Кацярыны, нябеснай заступніцы імператрыцы. Царыца зрабіла новай царкве падарункі: свой асабісты гардэроб і тры невялікія срэбныя падсвечнікі. У 1797 г. на багаслужэнні ў царкве прысутнічаў новы расійскі імператар Павел Першы і застаўся задаволены ўладкаваннем будынка і царкоўнай службай.
Аднак мінскія царкоўныя ўлады прыйшлі да высновы, што сабор знаходзіцца на вельмі няўдалым і непрывабным месцы. Сабор быў перанесены, пазбаўлены статусу кафедральнага і ператварыўся ў звычайную царкву.
Пасля выгнання войска Напалеона будынак царквы адрамантавалі на сродкі, выдзеленыя ўрадам. З гэтага часу цягам больш як стогадовага перыяду Кацярынінская царква на Нямізе выконвала ролю ідэолага расійскага самадзяржаўя. У 1871 г. храм амаль цалкам перабудоўваюць. Над царквой узводзіцца купал, перарабляецца іканастас. На сценах царквы наносіцца новы роспіс. Правую прыбудову царквы пераасвячаюць у імя Мікалая Цудатворца. Экстэр'ер аздабляюць мноствам дробных дэталяў у стылі правінцыйнага класіцызму, абсалютна чужога абліччу храма. З-за жоўтай афарбоўкі сцен царкву працяглыя часы называлі "жоўтай царквой". У 1911 г. ўлады зноў звярнуліся ў імператарскую археалагічную камісію з пытаннем пра рамонт.
У 1926 г. царква абвешчана помнікам архітэктуры і ўзята пад ахову дзяржавы. Аднак у 1933 г. савецкія ўлады царкву зачынілі, а яе маёмасць сканфіскавалі, прыстасаваўшы храм пад склад. Будынак падзялілі на тры паверхі, а роспісы зафарбавалі. У час Другой сусветнай вайны царква дзейнічала і нават была наноў распісаная. Пасля вызвалення Мінска ад нямецка-фашысцкіх захопнікаў будынак царквы быў перададзены пад жытло.
З канца 1960-х гг. будынак займалі Беларускі дзяржаўны архіў-музей літаратуры і мастацтва БССР і Беларускі дзяржаўны архіў навукова-тэхнічнай дакументацыі БССР. У 1972 - 1979 гг. храм рэстаўраваўся паводле праекта Мінскіх навукова-рэстаўрацыйных і вытворчых майстэрняў Міністэрства культуры БССР (архітэктар А. І. Курто), царкве быў нададзены першапачатковы выгляд.
У 1991 г. храм быў вернуты праваслаўнай царкве, у чэрвені яго асвяціў Патрыярх Маскоўскі і ўсяе Русі Аляксій II, а 7 снежня 1991 года ў ім аднавілі набажэнствы. Архівы ж перамясціліся ў будынак па вул. Кірылы і Мяфодзія, 4, у якім знаходзяцца і па сёння.