250px|thumb|Krzyż stojący przy wejściu do kościoła Parafia Narodzenia NMP w Paluzach – parafia rzymskokatolicka należąca do dekanatu Reszel archidiecezji warmińskiej
Historia parafii Została utworzona 20 czerwca 1409 roku. Parafia w Paluzach przed 1525 rokiem należała do archiprezbiteratu jeziorańskiego. Kościół w Paluzach pw. Najświętszej Marii Panny istniał już w 1355 roku. Konsekrował go 20 czerwca 1409 roku (data uznawana za powstanie parafii) biskup warmiński Henryk Vogelsang ku czci św. Krzyża, Matki Boskiej, św. Katarzyny i Wszystkich Świętych. Przed konsekracją kościoła proboszczem był Henryk Mahnbock, a później Baltazar Rabe. Po rozbudowie kościoła w 1890 roku, budynek świątyni ponownie konsekrował biskup Andrzej Thiel ku czci Matki Boskiej i św. Walentego w roku 1896.
We wsi oraz pośród zabudowy kolonijnej znajduje się kilka kapliczek i przydrożnych krzyży. Pierwsza wzmianka o szkole parafialnej z drugiej połowy XVI wieku. W parafii Paluzy w 1772 roku: urodziło się 21 nowych wiernych, zawarto 5 związków małżeńskich, zmarło 7 wiernych, komunię św. wielkanocną przyjęło 392 wiernych. W połowie XIX wieku do parafii należeli wierni ze wsi Łędławki.