Византийский царь Юстиниан I восстановил город и построил крепость, чтобы защищать северные рубежи своей державы. Но после смерти императора, в начале VII века, город разорили окончательно: забылось его имя, исчезли многочисленные памятники, до основания были уничтожены крепость и лагерь византийцев… Но осталась земля, осталось устье Савы и Дуная, остался Калемегданский гребень как вызов новым завоевателям.
Долгое время Белград оставался вне сербской державы, и только в 1284 году венгерский король Владислав I передал Мачванскую бановину с Белградом в пожизненное владение своему зятю – сербскому королю Драгутину, когда тот уступил престол своему младшему брату. После смерти Драгутина его младший брат Милютин хотел было удержать Белград, но сделать это ему не удалось, и в 1319 году город снова переходит под власть венгров.