Wieś Pałuki należała w XV w. do Pałuckich herbu Prawdzic, potem do wielu innych rodzin, a w XIX w. została zakupiona przez Wincentego Krasińskiego i przyłączona do ordynacji.
Parafia powstała prawdopodobnie w XIII w. Kościół w Pałukach pw. Wniebowzięcia NMP i św. Gotarda powstał zapewne w XIII w., choć pierwsza wiadomość o nim pochodzi dopiero z r. 1385, gdy ustalono granice parafii Ciemniewo. Na pocz. XVI w. proboszczem w Pałukach był kantor katedry płockiej Obidziński; możliwe, że on właśnie zbudował nową świątynię albo przynajmniej odnowił istniejącą. W 1512 r. ks. Obidziński uzyskał dla kościoła odpusty z okazji uroczystości: Wniebowzięcia NMP, św. Mikołaja, św. Gotarda i św. Tomasza Apostoła. W 1599 r. drewniana, konsekrowana świątynia posiadała dwie boczne kaplice: św. Jana Chrzciciela (północna) i św. Krzyża (południowa, zbudowana około połowy XVI w. przez Gotarda z Pałuk, kanonika łęczyckiego i proboszcza w Pałukach). Oprócz głównego ołtarza, w którego nastawie znajdował się tryptyk, istniały trzy boczne: Wniebowzięcia NMP, św. Mikołaja i św. Anny (z altarią, ufundowaną w 1531 r. przez Annę, kasztelanową liwską). Kościół ten spalił się prawdopodobnie ok. 1690 r.
Ks. Mateusz Muszyński w 1693 r. rozpoczął budowę nowego; prace dokończył następny proboszcz, ks. Jan Grabowski, który dzięki ofiarom parafian wyposażył świątynię w nowe ołtarze, szaty i sprzęty liturgiczne. Konsekrował ją 14 września 1698 r. sufragan diecezji płockiej i prepozyt kapituły biskup Marcin Załuski. W 1781 r., gdy proboszczem był ks. Stanisław Ostrowicki, wzmocniono podwaliny kościoła, który miał wówczas wymiary 18 x 7 m, i naprawiono dach.
Na pocz. XIX w. stan świątyni był już bardzo zły, w 1832 r. zawaliła się z powodu przegnicia elementów konstrukcyjnych. Zbudowano w tym miejscu niewielką kaplicę, która przez kilkanaście lat pełniła funkcję kościoła parafialnego. Obecną, murowaną, neogotycką, orientowaną świątynię według projektu Józefa Iżyckiego i Michała Jakuba Miklaszewskiego, wzniósł w latach 1842-1843 ks. Franciszek Ksawery Nałęcz, z fundacji gen. Wincentego Krasińskiego i ofiar parafian. Konsekrował ją 17 sierpnia 1845 r. biskup sufragan włocławski Tadeusz Łubieński.
W głównym neogotyckim ołtarzu z 1883 r. znajduje się obraz Matki Bożej Pocieszenia z XVII w., rzekoma kopia ołtarza z kościoła w Norymberdze. Na zasuwie obraz św. Gotarda, namalowany przez Antoniego Kolasińskiego w 1883 r.
W nastawach ołtarzy bocznych obrazy – po lewej: Serca Jezusowego, namalowany w 1889 r. przez Wojciecha Gersona i Matki Bożej Różańcowej pędzla Szymona Buchbindera z 1892 r., w ołtarzu prawym: obraz Matki Boskiej Anielskiej, kopia z XVIII w. według Murilla. Ambona i chrzcielnica z herbem Krasińskich z połowy XIX w. Organy wykonane przez Mateusza Melczarskiego z Łowicza z fundacji hrabiego Krasińskiego stanęły w świątyni po konsekracji, ale przed 1850 r., obecnie mają dwanaście głosów. W 1957 i 1959 r. ks. Tymoteusz Zalewski sprawił dwa nowe ołtarze boczne.
Na początku XXI w., gdy proboszczami parafii byli kolejno: ks. Józef Bolesław Pokorski i ks. Wacław Michalski, dokonano wielu prac renowacyjnych w pałuckiej świątyni; ufundowano nowe witraże, zakonserwowano i ozłocono ołtarz główny, dwa ołtarze boczne, dwa konfesjonały, ambonę i chrzcielnicę; wyremontowano zakrystię, kapitularz, wieżę i organy. W kościele zainstalowano nowe, energooszczędne oświetlenie. Naprawiono parkan i położono polbruk wokół kościoła, a także zbudowano przed nim parking. Nastąpił też gruntowny remont plebanii parafialnej. W 2011 r. postawiono pomnik św. Jana Pawła II. W 2020 r. odnowiono i pomalowano elewację kościoła.
Msze Święte:
Niedziela: 9:00, 10:30, 12:00
Dni Powszednie: 17:00 zimą, 18:00 latem
