Током постојања Архив се готово стално сусретао са проблемом неадекватног и недовољног простора, како за смештај запослених тако и за смештај архивске грађе. Зграде које је Архив користио нису ни по условима ни по капацитету одговарале захтевима једног државног архива, а у појединим периодима дешавало се да су се за смештај архивске грађе користиле просторије таквих амбијенталних карактеристика да се у њима стање архивске грађе погоршавало у односу на стање које је имала у тренутку преузимања.
Шездесетих година прошлог века учињен је покушај да се за Архив изгради наменски и адекватан објекат. Пројекат зграде Архива на Новом Београду, урађен је 1961. године, али због недостатка средстава никада није реализован.
Основан 1950, Архив је тек 1952. отпочео рад на заштити архивске грађе из своје надлежности. Почетком септембра 1952, Архиву су додељене две просторије за рад у згради на Теразијама 41, као и део подрума за смештај грађе. Исте године Архиву је додељена и недовршена зграда Евангелистичке цркве у Дринчићевој улици 1, а нешто касније добијене су са грађом и просторије у улици Драгослава Јовановића 9.
1969
Зграду у којој се и сада налази Архив је добио 1969. године, а целокупан простор почео је да користи од 1970, после исељења претходних корисника.
Скоро 20 година од оснивања требало је да прође па да Архив добије зграду довољно пространу за смештај архивске грађе. Извесно време смештајни капацитети били су довољни, али преузимање велике количине грађе у периоду 1991–1992. година поново је актуелизовало питање недостатка простора које је и сада нерешено.