Początki Paczółtowic sięgają XIV stulecia, jako że najstarszą źródłową datą, pod którą występuje „villa Pacoldi”, czyli posiadająca kościół parafialny wieś Pacolda, jest rok 1335. Ową datę odnotowano ponadto w wykazie tzw Świętopietrza. W latach 1350 – 1351 dokumentalnie zapisano z kolei określenie „Kościół z Paczółtowic”, po raz pierwszy posługując się tym samym znaną dziś nazwą wsi.
Ród Paczółtowskich, pieczętujący się herbem Topór, był właścicielem wsi do lat trzydziestych XV wieku Ostatni z rodu Jan Paczółtowski oraz zmarły w 1536 roku Stanisław są prawdopodobnie fundatorami tutejszej świątyni, budowanej w latach 1510 – 1515. Pod koniec XVII wieku w Paczółtowicach działała także szkoła, która kształciła do pracy w kamieniołomach dębnickich. Pracował tu m.in. jeden z pierwszych polskich mistrzów Adam Negowicz.
Ważnym wydarzeniem z życia Kościoła parafialnego pw. Nawiedzenia Najświętszej Marii Panny w Paczółtowicach było poświęcenie w 1960 roku przez biskupa krakowskiego Karola Wojtyłę dwóch nowych dzwonów. Wraz z zabytkowym dzwonem „Maria” (1535 r.) zostały one zawieszone osiem lat później na nowej dzwonnicy o metalowej konstrukcji, która stoi na terenie dawnego cmentarza przykościelnego. Ona również została poświęcona przez Karola Wojtyłę, który wówczas piastował już godność kardynalską.
Wśród zabytków należy natomiast wymienić ufundowany 1604 roku, bogato rzeźbiony i złocony ołtarz główny, w którym umieszczono łaskami słynący obraz Matki Boskiej z Dzieciątkiem. Obraz ten, jak również wiszące dziś po jego bokach dwa skrzydła, składały się na pierwotny, późnogotycki, namalowany temperą na lipowych deskach w latach 1460-1470, tryptyk Matki Boskiej Niepokalanie Poczętej. Co ciekawe, kiedy tryptyk był zamknięty, wierni mogli oglądać tworzących scenę Zwiastowania Archanioła Gabriela i Marię. Po otwarciu skrzydeł ukazywały się natomiast dwie święte dziewice: Barbara i Katarzyna Aleksandryjska.
W świątyni można ponadto podziwiać pochodzący z 1741 roku obraz patrona skalników i kamieniarzy św. Klemensa, datowany na przełom XVII i XVIII wieku obraz „Ukrzyżowanie” (malarstwo sztalugowe) czy obraz Chrystusa Frasobliwego z 1510 roku, który mógł należeć do pierwotnego wyposażenia kościoła. Wyjątkowy jest również pochodzący z drugiej połowy XVII wieku obraz Chrystusa w Tłoczni Mistycznej, na którym przedstawiono dwóch aniołów zbierających do kielicha wino symbolizujące przelaną za ludzkie grzechy krew Zbawiciela.
Manierystyczny ołtarz św. Mikołaja z początków XVII wieku został z kolei prawdopodobnie sprowadzony z Wawelu, a pochodząca z początku XVIII wieku ambona tworzy integralną całość z konfesjonałem. Zobaczyć warto również m.in. wykonaną w 1533 roku z brązu Chrzcielnicę, wspomniany Dzwon „Maria” z 1535 roku, datowany na 1658 rok marmurowy lichtarz pod paschał, organy z roku 1701 czy barokowe ołtarze św. Józefa i św. Rodziny.
