Nazwa wsi pojawia się po raz pierwszy w dokumentach w roku 1224 dzięki Wiesławowi z Probołowic. W roku 1326 była tu parafia należąca do dekanatu czarnocińskiego, plebanem był Paweł – musiał więc stać kościół. Długosz potwierdza istnienie drewnianego kościoła pod wezwaniem św. Jakuba arcybiskupa. W jego czasach /ok. roku 1470/ dziedzicem Probołowic i kolatorem był Piotr Gnoiński, proboszczem Włościbór, a dziesięcinę – prócz miejscowego plebana – otrzymywał także wiślicki kantor.
Nie wiemy czy pierwotny kościół się spalił, czy może znajdował się w stanie nie nadającym się do remontu, w każdym razie zastąpił go drugi, nowy kościół, który „stanął” w Probołowicach około roku 1500. Jego konsekracji dokonał w roku 1502 sufragan krakowski, Marian. Z wizytacji biskupiej z roku 1598 wynika, że kościół miał szczelny dach, prosty strop, okna w stanie dobrym oraz dzwonnicę z dwoma dzwonami.
W roku 1664 wizytujący parafię biskup Mikołaj Oborski. „zastał kościół …przez heretyków sprofanowany i dotąd nie rekoncyliowany” – pisze ks. Wiśniewski. W roku 1748 stan kościoła był już bardzo zły. Na cmentarzu stała dzwonnica – także w kiepskim stanie oraz kostnica.
W roku 1759 trzeci probołowicki kościół, stojący do dziś, „wystawił” ksiądz Jacek Kowalski, miejscowy proboszcz. Budowę poprzedziła rozbiórka starego obiektu, bowiem nowy powstał na tym samym miejscu. Opis z roku 1783 informuje o dobrym stanie świątyni /choć pokrycie nie starego przecież dachu było już poprawiane!/, opisując układ znajdujących się w niej pomieszczeń – niemal identyczny jak obecnie. Wspomina też o dzwonnicy, w roku „niniejszym” wyremontowanej. W roku 1842 wymieniono gontowe pokrycie kościoła. Pod koniec XIX stulecia wyremontowano podmurówkę – podnosząc ją wyżej, wymieniono przyciesie. Po ostatniej wojnie dokonano kilku „drobniejszych” remontów – wymieniono deski szalunków, odnowiono też polichromię.
Kościół jest pięknie położony – na zboczu stromego wzgórza, na skraju wsi. Jest orientowany ma trójnawowy, niemal kwadratowy korpus i prostokątne, trójbocznie zamknięte prezbiterium, którego szerokość równa jest szerokości głównej nawy. Od północy do prezbiterium przylega zakrystia, od południa skarbczyk. Przy nawie od strony południowej jest kruchta „porządna drewniana, razem z kościołem stawiana”. Na zewnątrz, na osi prezbiterium, znajduje się niewielka przybudówka o ażurowych ścianach, mieszcząca kamienną figurę Matki Boskiej Niepokalanego Poczęcia ustawioną na postumencie, która „jest pamiątką Jubileuszu ogłoszenia dogmatu 1854-1904 i darem od młodzieży” – pisze ksiądz Wiśniewski. Kościół ma ściany o konstrukcji zrębowej, ustawione na kamiennej podmurówce i wzmocnione lisicami. Nawę i prezbiterium nakrywają dwuspadowe dachy o więźbie wieszarowej, o takim samym kącie nachylenia połaci oraz jednakowym poziomie okapów, a zróżnicowanym kalenic, dawniej pokryte gontem, obecnie blachą. Nad dachami góruje wieżyczka na sygnaturkę, sześcioboczna, z arkadowa latarenką pod cebulastym hełmem. Ściany od zewnątrz oszalowane deskami „podwójnie na okładkę”, poniżej szalunku piaskowcowa podmurówka i podwalina osłonięta okapnikiem. Górą elewacje zamyka wydatny gzyms podokapowy. Nad prezbiterium wykonany jest strop zaokrąglony po bokach, w nawie pozorne sklepienie zwierciadlane – w nawach bocznych kształtem zbliżone do ćwierćkolebki.