Tokom postojanja Arhiv se gotovo stalno susretao sa problemom neadekvatnog i nedovoljnog prostora, kako za smeštaj zaposlenih tako i za smeštaj arhivske građe. Zgrade koje je Arhiv koristio nisu ni po uslovima ni po kapacitetu odgovarale zahtevima jednog državnog arhiva, a u pojedinim periodima dešavalo se da su se za smeštaj arhivske građe koristile prostorije takvih ambijentalnih karakteristika da se u njima stanje arhivske građe pogoršavalo u odnosu na stanje koje je imala u trenutku preuzimanja.

Šezdesetih godina prošlog veka učinjen je pokušaj da se za Arhiv izgradi namenski i adekvatan objekat. Projekat zgrade Arhiva na Novom Beogradu, urađen je 1961. godine, ali zbog nedostatka sredstava nikada nije realizovan.

Zgrade u kojima je bio smešten Arhiv

1952.

Osnovan 1950, Arhiv je tek 1952. otpočeo rad na zaštiti arhivske građe iz svoje nadležnosti. Početkom septembra 1952, Arhivu su dodeljene dve prostorije za rad u zgradi na Terazijama 41, kao i deo podruma za smeštaj građe. Iste godine Arhivu je dodeljena i nedovršena zgrada Evangelističke crkve u Drinčićevoj ulici 1, a nešto kasnije dobijene su sa građom i prostorije u ulici Dragoslava Jovanovića 9.

Terazije 41	Drinčićeva ulica 1	ulica Dragoslava Jovanovića 9
1953. Birčaninova ulica 1	1954. Savska ulica 35	1956. Kao privremeno rešenje za smeštaj građe, Arhiv je koristio tavanske prostorije u zgradi Beogradskog grafičkog zavoda
1964. Zmaj Jovina 12, zgrada Ekonomskog instituta	1966. Arhiv je dobio prostorije u podzemnim aneksima zgrade Palate federacije	1969. Zgradu u kojoj se i sada nalazi Arhiv je dobio 1969. godine, a celokupan prostor počeo je da koristi od 1970, posle iseljenja prethodnih korisnika.

Skoro 20 godina od osnivanja trebalo je da prođe pa da Arhiv dobije zgradu dovoljno prostranu za smeštaj arhivske građe. Izvesno vreme smeštajni kapaciteti bili su dovoljni, ali preuzimanje velike količine građe u periodu 1991–1992. godina ponovo je aktuelizovalo pitanje nedostatka prostora koje je i sada nerešeno.