Pierwszy ceglany kościół powstał do 1230 r. w 1253 r. książę wrocławski Henryk III i Władysław przekazali kościół praskim Krzyżowców z Czerwoną Gwiazdą.

12 listopada 1257 r. konsekrowano świątynie. Praktycznie cały XIV wiek aż do 1387 r. budowano nowy kościół w stylu gotyckim. W 1482 r. zakończono prace nad wieżą z hełmem.

Od 1525 r. aż do 1946 r. w kościele odbywały się msze w obrządku luterańskim.

W latach 1750 - 1761 Michał młodszy Engler wraz z członkami rodziny wzniósł barokowe organy, które spłonęły w pożaże świątyni w 1976 r.

Na placu przy kościele do XVIII znajdowała się nekropolia, o której przypomina zachowana brama między kamieniczkami Jasiem i Małgosią z napisem "Mors ianua vitae" ("śmierć wrotami życia").

W 1946 r. kościół staje się świątynią garnizonową.

Kościół przetrwał liczne pożary 1962 r. (latarnia hełmu wieży), 1975 r. (wieża kościoła), 1976 r. (pożar dachu, ornamentów i organów Englera).

Odbudowę rozpoczęto w 1980 r., ordynariat Polowy przywrócił papież Jan Paweł II 21 stycznia.

31 maja 2003 r. decyzją papieża Jana Pawła II ustanowiono kościół papieską Bazyliką Mniejszą.