Kościół pod wezwaniem Narodzenia Najświętszej Maryi Panny to niewątpliwie najważniejszy, najwyższy i widoczny z daleka obiekt w Paluzach.
Przywilej lokacyjny tej miejscowości nosi datowanie 1345 roku i wszystko wskazuje na to, iż zaraz po tym fakcie rozpoczęto budowę kościoła, istniał on już bowiem w roku 1355 pod wezwaniem Najświętszej Marii Panny. Jego konsekracji dokonał biskup Henryk Vogelsang w dniu 20 czerwca 1409 roku poświęcając go ku czci Świętego Krzyża, Matki Boskiej, Świętej Katarzyny i Wszystkich Świętych. Najprawdopodobniej w dniu konsekracji nie była to ta sama świątynia, przypuszcza się iż pierwotna uległa zniszczeniu i wybudowano ja na nowo. W roku 1890 kościół został rozbudowany, wydłużono wówczas jego nawę i dobudowano prezbiterium z zakrystiami ale niestety zniszczono też strop z polichromią z 1693 roku. Ponownej konsekracji świątyni dokonał biskup Andrzej Thiel w 1896 roku, ku czci Matki Boskiej i Świętego Walentego.
Kościół ten jest budowlą gotycką i orientowaną, murowaną z cegły na podmurowaniu z kamieni polnych. To świątynia salowa na rzucie prostokąta, z zakrystią od północy zamienioną na kaplicę chrzcielną i kruchtą od południa oraz kwadratową wieżą od zachodu. Wyposażenie i kościoła jest raczej nowe, utrzymane głównie w stylu neogotyckim. Godny uwagi jest barokowy chór muzyczny z malowanymi scenami ze Starego Testamentu, a także osiem obrazów Apostołów i rzeźby przedstawiające świętych. Zabytki te pochodzą z XVII i połowy XVIII wieku, podobnie jak dwa konfesjonały i różne cenne przykłady sztuki złotniczej. Obecnie kościół jest pod wezwaniem Narodzenia Najświętszej Maryi Panny, w roku 1967 wpisany został do rejestru zabytków.