Jabarkan Abad pertengahan dari Beograd

Pada tahun 442, wilayah Beograd dihancurkan oleh Attila. Pada tahun 471, wilayah ini dihancurkan oleh Theodoric yang Agung, yang kemudian meneruskan serangannya ke Yunani. Setelah kaum Ostrogoth meninggalkan wilayah tersebut untuk menyerbu Italia, orang-orang Gepid mengambil alih kota ini. Pada tahun 539, kota ini direbut kembali oleh Romawi Timur. Pada tahun 577, sekitar 100.000 orang Slavia datang ke Trakia dan Ilirikum dan menghancurkan kota-kota sebelum akhirnya bermukim. Suku Avar di bawah kepemimpinan Bayan I menaklukkan seluruh wilayah ini pada tahun 582. Menurut kronik Romawi Timur De Administrando Imperio, orang-orang Serbia Putih sempat berhenti di Beograd dalam perjalanan pulang. Mereka meminta tanah dari strategos dan akhirnya memperoleh provinsi di barat yang akan dikuasai sebagai bawahan Kaisar Romawi Timur Heraklius (610–641). Pada tahun 829, Khan Omurtag menjadikan Singidunum dan wilayah sekitarnya sebagai bagian dari Kekaisaran Bulgaria Pertama.

Catatan sejarah pertama yang menyebut nama Belograd berasal dari surat paus yang dialamatkan kepada penguasa Bulgaria Boris I yang bertanggal 16 April 878. Belakangan terdapat beberapa nama: Alba Graeca (kota Yunani), Griechisch Wiessenburg (kastil putih Yunani), Nandor Alba (kota orang-orang Bulgaria), Nandor Fejervar (kastil putih orang-orang Bulgaria), Castelbianco (kastil putih), dan Alba Bulgarica (kota Bulgaria). Kota ini diperebutkan oleh Kekaisaran Romawi Timur, Kerajaan Hungaria dan Kekaisaran Bulgaria selama sekitar empat abad. Kaisar Romawi Timur Basil II (976–1025) pernah menempatkan garnisunnya di Beograd. Kota ini juga pernah menerima tentara salib pertama dan kedua. Namun, ketika Kaisar Romawi Timur Friedrich Barbarossa melewati kota ini bersama dengan 190.000 tentara salib untuk turut serta dalam Perang Salib Ketiga, mereka mendapati bahwa kota Beograd telah hancur.

Raja Stefan Dragutin (berkuasa 1276–1282) memperoleh kota Beograd dari mertuanya, Stefan V dari Hungaria, pada tahun 1284. Kota ini dijadikan ibu kota Kerajaan Syrmia dan Dragutin dianggap sebagai Raja Serbia pertama yang menguasai Beograd sebagai vasal Kerajaan Hungaria.

Setelah berakhirnya Pertempuran Maritsa (1371) dan Kosovo (1389), Serbia mulai runtuh dan Kesultanan Utsmaniyah menaklukkan wilayah selatannya. Meskipun begitu, Kedespotan Serbia yang beribukota di Beograd masih terus melawan. Kota Beograd berkembang pada masa kekuasaan Stefan Lazarević, putra pangeran Serbia Lazar Hrebeljanović. Lazarević membangun sebuah kastil dengan benteng dan menara; saat ini hanya menara Despot dan tembok barat yang tersisa. Ia juga membentengi kembali tembok kuno kota, sehingga Kedespotan Serbia dapat menahan Utsmaniyah selama hampir 70 tahun. Pada masa itu, Beograd menjadi tempat pelarian orang-orang Balkan yang menghindari kekuasaan Utsmaniyah, sehingga jumlah penduduknya mencapai 40.000 hingga 50.000 jiwa.

Pada tahun 1427, penerus Stefan Đurađ Branković harus mengembalikan Beograd kepada Raja Hungaria, sehingga Smederevo menjadi ibu kota baru. Walaupun Utsmaniyah berhasil merebut sebagian besar wilayah Kedespotan Serbia, Beograd yang dikenal dengan nama  Nándorfehérvár dalam bahasa Hungaria berhasil dipertahankan dari pengepungan Utsmaniyah pada tahun 1440. Kota ini menjadi penghambat dalam upaya Utsmaniyah untuk menyerbu Hungaria, sehingga 100.000 pasukan Utsmaniyah mengepungnya pada tahun 1456, tetapi pasukan Kristen di bawah kepemimpinan Jenderal Hungaria Hunyadi János berhasil mempertahankannya. "Lonceng tengah hari" yang diperintahkan oleh Paus Kallistus III untuk merayakan kemenangan ini masih dibunyikan di dunia Kristen hingga kini.

Kekuasaan Utsmaniyah dan pendudukan Austria

Tujuh dasawarsa setelah pengepungan pertama, Beograd akhirnya jatuh ke tangan Sultan Suleiman yang Agung dan 250.000 pasukannya pada 28 Agustus 1521. Kota ini kemudian diratakan dengan tanah dan semua penduduk Ortodoks Kristennya dideportasi ke Istanbul, ke tempat yang semenjak itu disebut hutan Beograd. Beograd ditetapkan sebagai ibu kota distrik (Sanjak) dan kemudian menjadi kota Utsmaniyah terbesar kedua di Eropa dengan jumlah penduduk sebesar 100.000 jiwa. Kekuasaan Utsmaniyah juga membawa arsitektur Utsmaniyah (terutama dalam bentuk masjid) dan menambah nuansa Oriental di kota ini. Pada tahun 1594, pemberontakan yang dilancarkan oleh orang-orang Serbia dipadamkan oleh Utsmaniyah. Akibat pemberontakan tersebut, Wazir Agung Sinan Pasha memerintahkan pembakaran pusaka Santo Sava di muka umum di dataran tinggi Vračar. Gereja Santo Sava dibangun pada abad ke-20 untuk mengenang peristiwa ini.

Kota ini sempat diduduki tiga kali oleh pasukan Habsburg (1688–1690, 1717–1739, 1789–1791). Namun, Beograd selalu direbut kembali oleh Utsmaniyah dan kemudian dihancurkan. Selama periode ini, kota ini terkena dampak Migrasi Besar Serbia Pertama dan Kedua, yaitu peristiwa-peristiwa ketika ratusan ribu orang Serbia yang dipimpin oleh Patriark Serbia mundur bersama dengan pasukan Austria ke Imperium Habsburg dan menetap di wilayah Vojvodina dan Slavonia.