Jedna z miejscowych legend głosi, iż przed wieloma wiekami, w miejscu dzisiejszego kościoła parafialnego, dobiła do brzegu tratwa z transportem ściętego drzewa. Flisacy, wdzięczni za pokonanie niezwykle niebezpiecznego odcinka rzeki, pełnego wirów, które wielokrotnie rozrywały powiązane w tratwy pnie drzew, ofiarowali cały jego transport na budowę kościoła.
Kolejne drewniane świątynie trawiły pożary. Wzniesiony w 1728 roku staraniem księdza Mateusza Pozewskiego, konsekrowany w 1729 roku przez Stanisława Hozjusza, biskupa kamienieckiego, drewniany kościółek spłonął (wraz z całym wyposażeniem i archiwum dokumentującym prawie 600-letnią historię parafii) w czasie działań wojennych w roku 1944. Na jego miejscu, w latach 1950–1962 wybudowano według projektu architekta Zenona (lub Wiesława) Kononowicza nowy, murowany, bryłą i stylistyką nawiązujący do budowli romańskich. Jedynymi zabytkowymi elementami są dwa nieczynne już spiżowe dzwony. Legenda głosi, że dzwony zdjęte z kościelnej wieży podczas I wojny światowej w celu przetopienia na "armaty" odnalazły się po wojnie w Austrii i powróciły do Wieliszewa.