Kościół Wszystkich Świętych w Krościenku nad Dunajcem został wzniesiony z łamanego kamienia w I połowie XIV wieku. Istniał już w 1350 roku, choć był znacznie przesunięty względem dzisiejszego kościoła w kierunku Dunajca i nie posiadał wieży. Kościół z tego okresu był niewielki, miał wymiary 7x6 m, z kwadratowym prezbiterium 4x4 m. Prawdopodobnie w wyniku podmycia przez rzekę część pierwotnego prezbiterium osunęła się w pierwszej połowie XVI wieku. Do obecnych czasów zachowała się nawa pełniąca dziś funkcję prezbiterium. W 1546 roku, za ks. Marcina z Piotrkowa, kościół został powiększony o obecną nawę (obecne prezbiterium jest częścią dawnej nawy). Pozostałością po dawnym prezbiterium jest istniejąca przybudówka (z kryptą grobową pod ówczesnym głównym ołtarzem). W XVII wieku dobudowano wieżę. W pożarze w 1755 r. spłonął dach i drewniane stropy, zaś w 1788 r. uszkodzona została wieża i sufit w nawie. W następnych latach zwieńczono wieżę dachem hełmowym, w kształcie który możemy oglądać do dziś. W 1796 i 1802 na wieży umieszczono dwa dzwony, które niestety zostały zarekwirowane w czasie I wojny światowej.