A falu gyors fejlődése következtében a 19. század második felében kicsi lett a templom. Ezért a falu lakói Bernkopf Károly plébános felhívására elhatározták, hogy nem a régi templomot fogják megjavítani, hanem egy teljesen újat építenek.
Erre a célra külön templomépítő bizottság alakult, amely első ízben 1902. március 2-án a plébánosnál jött össze. Tagjai Kubányi Alajos, Kovács Mihály, Erdélyi Lajos, Gútai Lajos, Győri Ferenc, Győri János, Gáspár Alajos, Győri András, Horváth József, Juhos István, idősebb Juhos Ádám, Juhos János, Bugár Gábor, Bugár Imre, Petrovics Károly, Takács Ferenc, Gáspár Márton, Győry Kálmán, Bartalos Antal, Kürty Ignácz, Szőcs János, Győry Mihály, Kelemen György, Nagy Pál és Gútai János voltak. A bizottság világi elnöke Horvatovich József, a jegyzőkönyvvezető Bencze Kálmán kántortanító volt. A tervek elkészítésére Schneider József vágsellyei mérnököt kérték fel, aki 1902. március 13-án személyesen meghallgatta a bizottság elképzeléseit a jövendő templomról. A kiadások csökkentése céljából a falu elvállalta az építkezéshez szükséges anyagok szállítását. A bizottság a készítendő tervek maximális árát 200 koronában szabta meg.

A templom első tervét 1902. április 2-án mutatta be a mérnök a faluban. Az építkezéshez szükséges anyagi fedezet megteremtésére a templomépítő bizottság olyan határozatot fogadott el, hogy a lakosok minden magyar hold föld birtoklása után 5 korona pénzösszeget fizessenek. Az így nyert pénzösszeg 18 ezer koronát tett ki. Ezenkívül még gyűjtést indítottak a helyi lakosok körében. 1902 októberére megszerezték az érseki helynök módosító javaslatait, amelyek alapján az eredetileg tervezett vasoszlopokat téglaoszlopok váltották fel. 1902 őszére már a téglát és a homokot is beszerezték a nádszegiek az építkezéshez, és ekkorra már 30 ezer koronájuk gyűlt össze. Az eredeti költségvetésből a keresztelőkútra és három oltár elkészítésére szánt 8 100 korona költséget leszámították, ezt az összeget a jobb módú hívek ajándékozták e célra. A templom elkészítését 1903-ra tervezték, de az anyagiak megszerzése több időt vett igénybe. Az építkezés kivitelezésére először a Kittler és Gratzel céget kérték fel, természetesen a kivitelező cég kiválasztása nyilvános felhívás után történt. A Kittler és Gratzel cég Malatinszky műépítészt bízta meg a pontos kivitelezési terv elkészítésével. Ezt úgy kellett volna elkészíteni, hogy az építkezés költsége ne haladja meg az 50 ezer koronát. Mivel a költségvetés ennél jóval magasabb lett – 94 ezer koronát tett ki -, a templomépítő bizottság felkért Pozsony megyéből három építészt – Hanzel Józsefet Szencről, Tomaschek Jánost Nyitráról, valamint az uradalmi építészeket Pozsonyból – a tervezet elbírálására.

Az építészek véleményéről nem maradtak fenn pontos adatok, azonban minden bizonnyal komoly módosításokra került sor, mivel a visszaemlékezésekben a templom tervezőjeként Elefánty István pozsonyi mérnök van feltüntetve. A kivitelezést Hanzel József cége végezte. Annak ellenére, hogy az építkezés költsége meghaladta az eredeti elképzeléseket, a templom építése 1903 áprilisában megkezdődött, miután a régi templomot lebontották. Az előző templom anyagából csak a száraz téglákat használták fel az új templom építésekor. Az építkezésbe az Esterházy család is besegített, ők adták az építkezéshez szükséges meszet. A téglát helyben égették. Az építkezés során több gond merült fel. Az iszapos talaj miatt erős alapot kellett építeni. Ezt úgy oldották meg, hogy a betonalapok alá 4 méter hosszú, 40×40 cm vastagságú tölgyfacölöpöket vertek.
Ezek fölé tölgyfagerendák kerültek soronként keresztbe fektetve 3 m mélységben, ezek fölé pedig beton került, vasgerendával megerősítve. A szigetelés után júniusban elkezdődött a falazás. A jó ütemben folyó munkákat lelassította az 1903 június 13-án betört árvíz. A munkákat csak ősszel folytathatták. A falak 1904 augusztusára készültek el – ekkor már misét is tartottak az új templomban, egyébként az iskola épületében voltak a szentmisék az építkezés ideje alatt – november végére pedig befejezték a külső építkezési munkákat. A kereszt a torony tetejére 1904 október 25-én került fel.
„Tenger népség vette körül az új templomot… Röviden megemlékezvén azon nagy szerencsétlenségről, mely Nádszeget a legutóbbi nyár folyamán, az árvíz által érte, dicsérőleg hangoztatá, hogy habár ezen súlyos árvízveszély, mely az egész községet elöntötte, s minden épület és lakóháznak alapjait megingatta, de örvendetes tudomással kell vennünk, hogy ezen derék község jánborlelkű híveinek, igazi erős hitét mégsem volt képes érinteni. Most dacára a rettentő csapásnak, inkább önmaguktól megtagadva mindent, a templom építése körül a legnagyobb lelkesedéssel buzgólkodtak.”
(Huszár István, akkori királyrévi plébánosnak a keresztszentelési szertartásról nyomtatásban megjelent füzetéből.)