Od časa Keltov, ki so se na tem prostoru naselili prvi in naselje poimenovali Singidunum, do prve srbske prestolnice je preteklo več kot 1600 let.
Slovansko ime Beograda je prvič omenjeno v pismu rimskega papeža Janeza VIII. bolgarskemu knezu Borisu 16. aprila 878.
V letih 1403–1427 Beograd prvič postane srbska prestolnica despota Stefana Lazarevića (1389–1427). Njegova država je bila ena od najtrdnejših v Evropi. V mestu so bile cerkve, šole, bolnišnica, sirotišnica, gostišče s prenočišči. Poleg madžarskega kralja Sigismunda in dvaindvajsetih evropskih aristokratov je na ustanovni listini Zmajevega reda kot drugopodpisani tudi Stefan Lazarević. Despot je očaral Evropo, kronisti so ga poimenovali celo kot mesec med zvezdami.
Danes so iz despotovega časa na Kalemegdanu ohranjena le vhodna vrata v obzidju in stolp.