Според ископувањата од 2006 година, под темелите на црквата била откриена гробница, кој датира од околу 410 година[1]. Ова дополнително го потврдил фактот за важноста на Вестминстер во тоа време. Првите податоци за црквата датираат од околу 1222 година. Сепак се смета дека таа била реконструирана во времето на Хенри VIII, во 1542 година.
Црквата успеала да го преживее Големиот лондонски пожар од XVIII век, но сепак морала да биде реновирана. Така, новиот објект бил започнат во 1721 година, а се завршил пет години подоцна[2]. За главен архитект бил избран Џејмс Гибс. Самиот облик на оваа црква бил широко критикуван, главно поради обвинувањата на поголемиот дел од месните жители дека црквата била копија на оние цркви кои во тоа време се граделе во САД[3].