Леополдова капија налази се у најстаријем делу београдских бастионих фортификација, а њена изградња започела је непосредно након аустријског освајања града 1688. године. Капија није била завршена одмах, већ неколико година касније, у току радова којима је руководио Андреа Корнаро.

Садашња монументална барокна фасада заправо је млађа од саме капије, направљена је у време великих аустријских радова на обнови тврђаве, у трећој деценији 18. века. Иницијали који су уклесани над луком капије L. P. – Leopoldus Primus – припадају цару Леополду I (1640–1705), за време чије владавине је Београд први пут дошао у посед Аустрије. То је вероватно био разлог због ког је капија у време грађења нове фасаде посвећена успомени на овога цара, добивши по њему и своје садашње име.