Istorijski arhiv Beograda kao jedan od najmodernijih arhiva u zemlji, odigrao je značajnu ulogu u razvoju arhivske službe Srbije. Iako nema ingerencije matičnosti, uvek je po svojoj organizaciji, kadrovima i poslovima koje je obavljao predstavljao uzor mnogim arhivima.
Povod za nastanak ove institucije bio je, pre svega, da se zaštiti i sačuva izuzetno značajna građa Zemunskog magistrata, nastala još u XVIII veku. Upravo zbog toga, na predlog prosvetnog odeljenja Izvršnog odbora narodnog odbora grada Beograda, na sednici 26. septembra 1945. godine, doneta je Odluka da se osnuje samostalna ustanova «Gradski arhiv», sa zadatkom da prikuplja originalne dokumente društvene i privatne zaostavštine čiji je rad vezan za razvoj Beograda i Zemuna. Od osnivanja Arhiv je bio u sastavu Gradske biblioteke, da bi se 1947. godine odvojio i nastavio da deluje kao samostalna institucija.
Od 1954. godine nalazio se u zgradi bivše Klasne lutrije (ugao Vasine i Zmaj Jovine ulice).
Sadašnji naziv Arhiv je dobio Odlukom Gradskog veća i Izvršnog odbora grada Beograda na sednici održanoj 24. januara 1958. godine.
Upisan je u Registar Trgovinskog suda u Beogradu, rešenjem ISu-5/97 pod brojem 5-222-00, kao ustanova kulture od posebnog društvenog značaja, koja u okviru svoje delatnosti vrši zaštitu arhivske građe u registraturama, zatim preuzimanje, sređivanje, obradu, korišćenje i publikovanje arhivske građe.
Nadležnost Arhiva obuhvata područje Skupštine grada Beograda odnosno svih 17 gradskih opština.
Vremenom su prostorije i depoi postali tesni, jer je tokom godina Arhiv preuzeo veliki broj fondova. Zbog toga je 1963. napravljen elaborat budućeg namenskog objekta, po projektu Milana Jerkovića. Projekat je prihvaćen u Skupštini grada, a investitori su bili Gradski komitet Saveza komunista Srbije Beograda, Skupština grada Beograda i Gradsko stambeno preduzeće, dok je Direkcija za izgradnju Novog Beograda obezbedila lokaciju. U periodu od 1969. do1972. godine objekat je sazidan.
Zgrada je zvanično primljena 16. januara, a svečano otvorena 15. oktobra 1973. godine.
Površina terena na kome je sazidan objekat iznosi 7 200 m2, od toga 4 700 m2 korisne površine, i to: kancelarije, hodnici i druge prostorije 1 500 m2, radionice 480 m2 čitaonica 120 m2, galerija 200 m2, depoi 2 400 m2.