Kościół został wzniesiony w latach 1888–1904 według wyłonionego w konkursie projektu Józefa Piusa Dziekońskiego (przy współpracy Ludwika Panczakiewicza). Do udziału w konkursie dopuszczono wyłącznie architektów krajowych. Nadesłano łącznie 25 prac. Drugie miejsce zajął Władysław Marconi, a trzecie Ignacy Jórski. Przed zatwierdzeniem dokumentacji dokonano zmian w projekcie, wymuszonych względami oszczędnościowymi (m.in. skrócono korpus główny o jedno przęsło i ograniczono kamienny detal na rzecz cegły). W dniu wmurowania kamienia węgielnego zebrane fundusze wynosiły ok. 50 tys. rubli, z czego 6 tys. rubli podarowała Aleksandra Potocka.
Z uwagi na podmokłość terenu, zlokalizowanego na nadwiślańskich błoniach, konieczne było zastosowanie wzmocnionych fundamentów. Do budowy kościoła zamówiono cegły o podwyższonej wytrzymałości mechanicznej wytwarzane ręcznie w zakładach Kazimierza Granzowa.
W 1890, w związku z wyczerpywaniem się środków finansowych, wystąpiono do władz rosyjskich o dotację w wysokości 100 tys. rubli. Przyznana dotacja, wypłacana w ratach, pozwoliła na kontynuowanie budowy w kolejnych latach.