A Bazilika építkezése 1851-ben kezdődött és 1889-ben befejeződött. A terveket Hild József készítette 1845-ben és építését is ő kezdte el 1851-ben. Az építész halála után az építést 1867-től Ybl Miklós folytatta, majd Kauser József fejezte be.
A városrészt, amiben a templom épült, Lipótvárosnak nevezték el II. Lipót koronázási emlékére. Ezért a templomot is Szent Lipót templomnak nevezték el. 1896. május 7-én Lollok Lénárd plébános javasolta, hogy a bazilika Szent Lipót helyett Szent István nevét viselje.
1897-ben kezdték a Szent István nevet használni. Addig a főkapu fölött a Szent Lipót relief volt, amit levettek. A relief megmaradt, jelenleg az urnatemetőben van.

„III. (Szent) Lipót (1073 – 1136) osztrák őrgróf (1095 – 1136) Ausztria, Bécs, Alsó-Ausztria és Szent Flóriánnal együtt Felső-Ausztria védőszentje.” Monostorokat alapított: Klosterneuburg, Heiligenkreuz, Kleinmariazell és Seitenstetten. Ezért avatták szentté 1485-ben.

---