Kostel byl součástí rozsáhlého stavebního komplexu rytířského řádu johanitů, kteří u nás obnovili svojí činnost na sklonku roku 1989. Členové kdysi velmi mocného Maltézského řádu si říkají johanité, podle svého patrona sv. Jana Křtitele. Kostel stojící mezi ulicemi Saskou, Lázeňskou s Velkopřevorským náměstím má několik pojmenování. Říká se mu Panny Marie pod řetězem či „konec mosta“, nebo též U Maltézů. Konec mosta proto, že jako jeden z nejstarších malostranských kostelů stál nejblíže u Juditina mostu, později u mostu Karlova. Teprve později tady byl vystavěn Saský dům. Pod řetězem proto, že brána do klášterního dvora byla uzavíraná řetězem. Podle pověsti prý dokonce zlatým.
Původně raně gotická stavba kostela vznikla v polovině 13. století v místech románské baziliky. Kostel byl dvakrát zničen ohněm. Za husitských bouří v roce 1420, kdy byl navíc vyrabován celý areál, a v roce 1503. V 17. století poté barokně upraven patrně Carlem Luragem. Tak se stalo, že kostel se stal pouze stínem dřívější starobylé stavby. Z jeho gotické minulosti zbylo pouze průčelí a dvě snížené věže.
Právě věže na západní straně, vysoké 32 m, jsou počítány mezi takzvané kusé věže. Původně byly vyšší, ale po požárech došlo k jejich snížení. Silné hranolové věže z pečlivě opracovaných opukových kvádrů jsou kryty jehlancovými střechami a svá původní gotická okna mají zazděna. Věže podpírají mohutné nárožní pilíře.
