Kostel býval středem opevněného útvaru komendy řádu johanitů (maltézských rytířů) na strategicky významném místě u předmostí bývalého Juditina mostu. Klášter založil český král Vladislav II. V r. 1169 jako první johanitskou komendu v Čechách. Král daroval řádu okolní pozemky včetně západní části ostrova Kampy. Postupně zde bylo postaveno cca 50 domů spadajících pod jurisdikci řádu.

Původní románský trojlodní kostel byl větší než dnešní stavba a zachovaly se z něj zbytky v nynějším nádvoří (arkády na jižní zdi) a v postranní lodi dnešního kostela. Křížová klenba je pozůstatkem románské baziliky. V pol. 13. stol. Byl kostel rozšířen o raně gotické kněžiště.
Rozsáhlá gotická přestavba celého trojlodí započala v pol. 14. stol., kdy byla zbořena románská bazilika. Kolem r. 1375 byla vystavěna gotická předsíň v západní části a u ní kolem r. 1389 dvě mohutné hranolové věže. Novogotické cimbuří je z r. 1836. Dále již stavba nepokračovala a tak ze zbořeného románského trojlodí se stalo nynější nádvoří mezi věžemi s předsíní a vlastním kostelem. Ten byl přestavěn z raně gotického kněžiště za velmistra Matouše Děpolta z Lobkovic na přelomu 16. a 17. stol. Dnešní podobu získal při barokní přestavbě v l. 1640 - 60 podle projektu C. Luraga. Ve štítu kostela je umístěna dřevěná, pozdně gotická socha Madony.
Hlavní oltář s řezbami představujícími výjevy ze života apoštola Pavla je od J.P.Vendy z r. 1730. Kazatelna asi od téhož autora je z doby před r. 1750. Sochy světců na konzolách hlavní lodi jsou od J.J. Bendla (po r. 1651). Hlavní oltářní obraz (P. Marie a Jan Křtitel - pomocníci maltézských rytířů v bitvě s Turky u Lepanta r. 1571) je dílem Karla Škréty ze 60. let 17. stol. Od Škréty je také obraz sv. Barbory na bočním oltáři. V hlavní lodi stojí mramorová socha velkopřevora Rudolfa Coloredo-Walsee, který se v 17. stol. zasloužil o přestavbu kostela a kláštera. Socha je od E. Maxe z pol. 19. stol. Křížová cesta na stěnách kostela je od řádového malíře Vachka. Tepané mříže ze 16. a 17. stol byly doplněny novými podle návrhu J. Fanty. Kostel prošel rozsáhlou renovací v l. 1965 - 87.

Text: historie
15.9. 2003 - web