Singidunum su osvajali mnogi osvajači, poput Huna, Sarmata, Ostrogota i Avara - pre dolaska Slovena oko 630. godine nove ere. Prvi zapisi o slovenskom imenu Beograd datiraju iz 878. godine, za vreme vladavine Prvog bugarskog carstva. Grad je ostao predmet razmirica između Vizantije, Mađarske i Bugarske naredna četiri veka.
Grad konačno prelazi pod vlast Srba kao deo Srema 1284. godine. Prvi srpski kralj koji je vladao Beogradom bio je Stefan Dragutin (1276-1282), vladar Kraljevine Srema, kog je dobio na poklon od svog zeta, mađarskog kralja Ladislava IV. Nakon velikih gubitaka u Kosovskom boju 1389. godine, Srpsko carstvo počinje da se raspada i njegovi južni delovi velikom brzinom prelaze u ruke Turaka Osmanlija. Ipak, sever je dugo odolevao. Srpski despot Stefan Lazarević dobio je Beograd od ugarskog i rimskog kralja Žigmunda Luksemburškog, nakon što je postao njegov vazal. Godine 1403. Stefan Lazarević je proglasio Beograd svojom prestonicom. U narednom periodu, Beograd je doživeo veliki uspon. Ponovno su utvrđene stare zidine grada, zajedno sa zamcima, a crkve i tvrđave obnovljene, što je pomoglo da grad odoleva navalama Turaka čak 70 godina.
U ovo vreme, Beograd je postao utočište mnogim balkanskim narodima koji su bežali od vlasti Osmanlija. Veruje se da je broj stanovnika u ovo vreme dostizao i 40.000-50.000. Tokom vladavine Đurađa Brankovića, veći deo despotstva dospeva pod tursku vlast, međutim, Beograd dolazi pod zaštitu mađarskih kraljeva. Turci su želeli da pokore Beograd jer im je predstavljao prepreku u daljem napredovanju ka centralnoj Evropi. Napali su 1456. kada se odigrala čuvena Opsada Beograda gde je hrišćanska vojska pod vođstvom Sibinjanin Janka uspešno odbranila grad od turskog napada.
