Prvo utrđenje na ovoj lokaciji podigla su keltska plemena u trećem veku pre nove ere, pod imenom Singidunum. Kasnije su u vreme Rimljana ovde je bazirala IV legija Flaviusa, i građansko naselje pored tvrđave polako je počelo da se razvija. Međutim, Singidunum su 441. potpuno zbrisali Huni. Grad je obnovio car Justinijan, koji je Kalemegdan ogradio jakim zidinama (Beograd je u to vreme bio deo Vizantijskog carstva). Slovensko ime Beograd prvi put je zabeleženo u IX veku. 

Kalemegdan, odnosno Beograd je u srpske ruke pao tokom vladavine kralja Dragutina u XIII veku, ali se najviše razvio za vreme despota Stefana Lazarevića, koji je i osnivač srpske prestonice. On je stvorio jaku ekonomsku, društvenu i obrazovnu osnovu grada. Beograd ubrzo postaje najveća srpska naseobina, a Stefan Lazarević na gornjem gradu zida sebi tvrđavu. Nakon njegove smrti, Beograd ponovo osvaja Austrougarska i on postaje jedan o retkih gradova koji uspeva da zaustavi Turke i spreci njihov dalji prodor na sever.

Beograd se prvi put uspešno odbranio od Turaka 1440, a drugi put 1456. godine u čuvenoj bici "Antemurale Christianitatis" (odbrana hrišćanstva), u kojoj je Janos Hunyadi (Sibinjanin Janko) porazio sultana Mehmeda II. Ipak, Turci 1521. godine osvajaju Beograd i grad ostaje u turskim rukama narednih 150 godina.

Godine 1688. Kalemegdan na kratko opet pada u austrijske ruke, a pobeda 1717. dopušta im da počnu da razvijaju grad. Stilovi gradnje su se promenili i izgled grada je iz orijentalnog prešao u barokni. Postavljena je nova odbrambena struktura iz koje datira i današnji zvezdast oblik tvrđave. Beograd se u to vreme smatrao neosvojivim - nažalost, Austrija je grad izgubila sporazumom 1739. godine i ne želeći da ostavi Turcima tajne savremene arhitekture, tokom svog povlačenja je sistematski razorila grad. Poslednje veliko osvajanje grada dogodilo se 1807. tokom Prvog srpskog ustanka, a Turci su 1867. konacno predali grad Mihailu Obrenoviću.

U svojoj dugoj i krvavoj istoriji, Kalemegdan je rušen preko 40 puta, a posledice ratova i osvajanja su vidljive na današnjem izgledu tvrđave. Na određenim mestima može se videti nekoliko slojeva zidina različite strukture i načina gradnje, koji potiču iz različitih istorijskih perioda.