História farnosti sa začala písať už niekedy na začiatku 14. storočia. Okolo roku 1300 totiž tunajší zeman Ondrej nechal pre svoju potrebu vystaviť prvý kostol zasvätený sv. Jánovi apoštolovi. Neskôr jeho príbuzní z Bodíc postavili druhý kostol sv. Ladislava. Patronícium palúčanského kostola bolo okolo roku 1500 po jeho prestavbe zmenené na sv. Žofiu.
Kostol sa v druhej polovici 17. storočia dostala do rúk evanjelikov. Protestantskí kazatelia následne vo farnosti pôsobili až do roku 1677, kedy sa kostol vrátil do rúk katolíkov. Od tohto obdobia až do roku 1960 boli sídlom farnosti Bodice a Palúdzka bola filiálkou. Celkovo sa v Palúdzke vystriedalo 14 farských správcov, ďalších 23 bolo správcom v období, keď boli sídlom Bodice a počas pôsobenia evanjelikov sa vystriedalo 7 kazateľov.
Pôvodný gotický kostol v Bodiciach sa zachoval až dodnes. Takýto príbeh však nemal gotický kostol v Palúdzke. Ten niekedy na začiatku 19. storočia zanikol. Pravdepodobnou príčinou bola nestabilita svahu, na ktorom bol vystavaný. Z kostola sa dokázateľne zachoval oltár Klaňania troch kráľov zo začiatku 16. storočia, ktorý je v zbierkach Slovenského národného múzea. V roku 1854 bol však v Palúdzke postavený nový kostol, ktorý bol postavený z iniciatívy miestneho rodáka, biskupa nitrianskeho Imricha Paluďaia.
Ten financoval rovnako aj postavenie kaplnky Jána Nepomuckého z roku 1856, ktorá sa nachádza západne od kostola pri potoku Demänovka. Pod kaplnkou sa nachádzajú ostatky šľachticov Paluďaiovcov prenesené z pôvodného kostola. Pod novým kostolom sú taktiež uložené pozostatky zemanov tohto rodu, vrátane kráľovského radcu Imricha Paluďaia. Kostol bol v roku 1943 vymaľovaný Mikulášom Štalmachom.
Pre viac informácii o histórii a kostoloch prejdite na: