Obecny kościół parafialny pod wezwaniem Nawiedzenia Najświętszej Maryi Panny pochodzi z początku XVI wieku. Prowadzą do niego dwa wejścia – brama z figurami Matki Boskiej i Chrystusa oraz nieco skromniejsze wejście od strony południowej. W części południowo-wschodniej jest kamienna grota mieszcząca figurę Matki Boskiej z Lourdes.

W barokowym, bogato złoconym ołtarzu, wykonanym z czarnego wapienia dębnickiego umieszczono obraz Matki Boskiej z Dzieciątkiem, który powstał około 1460–1470 roku. Namalowany jest temperą na desce lipowej i zdobi barokową nastawę ołtarza głównego. Wizerunek przedstawia Maryję z Dzieciątkiem stojącą na łące pełnej kwiatów i ziół, a za nią w tle goreją drzewa. Otaczają ją promienie słońca, a u stóp ma księżyc. Dopełnieniem obrazu są dwa małe anioły w górnych narożach, trzymające szarfy z napisami „Regina coeli letare alleluia quia quem meruisti portare”. Regina coeli, czyli królowa nieba, miała według wielu wyznawców chronić przed zarazami.

Ten właśnie obraz był niezwykle ważny dla mieszkańców Paczółtowic. Uważali, że modlitwa przed nim może skutecznie pomagać odsunąć nieszczęścia, takie jak pacyfikacja wsi w czasie II wojny światowej. To wydarzenie upamiętniają dwie tablice umieszczone w kościele: jedna przy ołtarzu, druga przy wejściu do kościoła. Ludzie uważają też, że cudowna moc Maryi chroni ich przed anomaliami pogodowymi, gdyż otula ich ona swoim płaszczem.

Do najcenniejszych zabytków malarstwa zachowanych w paczółtowickim kościele należy obraz wotywny przedstawiający Chrystusa oczekującego na mękę, pochodzący z początku XVI wieku. 

Inne zabytki w kościele to gotycki krucyfiks umieszczony w przedsionku (kruchcie) pod wieżą i obraz Chrystusa Frasobliwego. Co ciekawe chrzcielnica z brązu zrobiona jest z dział zdobytych w czasie wojen. Pochodzi z XVI wieku i łączy w sobie cechy stylu gotyckiego i renesansowego. Ciekawy jest eksponowany w kruchcie barokowy obraz Chrystusa w Tłoczni Mistycznej z XVII wieku oraz obraz świętego Mikołaja z elementami rzeźbionymi w drewnie, a także okute blachą drzwi prowadzące z prezbiterium do zakrystii.

Zabytkowe organy barokowe to już początek osiemnastego wieku. Na ścianach i stropach kościoła widnieje polichromia z końca wieku XIX. Na ścianie prezbiterium i nawy zachowały się fragmenty malowideł z drugiej połowy XVII wieku, przedstawiające sceny Męki Pańskiej. Ponadto, w kruchcie świątyni zobaczyć można grupę niewielkich barokowych figur, przedstawiających różnych świętych.

W kamienny mur otaczający teren kościelny wmurowane są płyty i epitafia z marmuru dębnickiego z XVII i XVIII wieku. Świątynia znajduje się na Szlaku Architektury Drewnianej.