Parafia Podstolice jest jedną z najstarszych w Archidiecezji Krakowskiej.
Dokładny czas powstania pierwszej świątyni w Podstolicach jest trudny do ustalenia, ponieważ nie zachowały się żadne dokumenty poświadczające ten fakt. Zapewne istniała już przed 1348 rokiem, gdyż z podlegającej dekanatowi Szczyrzyc odprowadzano tak zwane świętopietrze. W „Słowniku geograficznym Królestwa Polskiego i innych krajów słowiańskich” jako czas powstania parafii w Podstolicach podano 1292 rok, natomiast w „Elenchus venerabilis cleri saecularis quam regularis dioeceseos Cracoviensis” znalazł się zapis, że erygowanie miało miejsce w 1291 roku, co zostało powszechnie przyjęte. Jednym z warunków powołania nowej parafii było istnienie kościoła. Określenie czasu budowy pierwszego kościoła w Podstolicach jest trudne do ustalenia. W zapisie inwentaryzacyjnym z 1754 roku został szczegółowo opisany poprzedni, nieistniejący kościół podstolicki, gdzie określany bywa jako „stary i już miejscami popróchniały” co sugeruje jego kilkusetletnią bytność.
Była to budowla orientowana, jednonawowa z niewielką wieżą nad wejściem oraz niewielką wieżyczką na sygnaturkę. Ściany budynku przeprute były 3 oknami z szybami wprawionymi w ołów z żelaznymi kratami i jedno na chórze bez szyb. Bryłę kościoła obiegały także tak zwane soboty. Dzwonnica była wolnostojąca. Wewnątrz, na połączeniu prezbiterium i części nawowej znajdowała się belka tęczowa z grupą Ukrzyżowania. Poniżej, pośrodku usytuowana była kamienna chrzcielnica. Posadzka była jedynie częściowo wykonana. W drugiej połowie XVIII wieku stan kościoła w Podstolicach przedstawiał się niekorzystnie.
Pierwsze próby ratowania wiekowej świątyni podjął ówczesny proboszcz Stanisław Gorczyński, pełniący posługę w latach 1781-1795, twierdząc, że „wszyscy Plebani, bądź intratnych, lub szczupłych dochodów w obowiązku koniecznym zostają starać się o utrzymywanie w porządku regularnym powierzonych sobie Kościołów (…) nie zasłaniając się trudnościami Duchownemi, bo Duchowość ma swój czas użycia o szczęście swoich Owieczek; zaś staranność o Dobro porządku ma właściwe z czynności usiłowanie”. Księdzu Gorczyńskiemu udało się uzyskać od Wysokiego Gubernium kwotę 6000 złp na cele remontowe. W ramach tego dofinansowania wymieniono odeskowanie wnętrza oraz pokrycie dachowe. Wykonano nowe okna oraz drzwi prowadzące z zakrystii na ambonę. W 1836 roku w całym kościele wyłożono nową, kamienną posadzkę, natomiast w 1858 roku wymieniono 2 okna. Częściowy remont dachu został przeprowadzony w 1862 roku, prace dotyczyły głównie znacznej jego powierzchni nad zakrystią. Wówczas także wymieniono gont na dzwonnicy. Intensywny w prace mające na celu poprawę stanu architektury kościoła był także 1864 rok. Udało się wówczas wymienić kolejne 2 okna, odrestaurować wieżyczkę na sygnaturkę oraz położyć nową podłogę na chórze. Wszelkie powyższe działania mające na celu utrzymanie wiekowej świątyni świadczyły o sporym zaangażowaniu tak kolejnych proboszczów, jak i miejscowej ludności. Mimo to w drugiej połowie XIX wieku podjęto decyzję o budowie nowej świątyni, którą wzniesiono w 1870 roku, w miejscu starego rozebranego kościoła. Fundusz na ten cel zasilały nie tylko datki społeczności parafialnej, ale także m.in. dzięki sprzedaży obligacji wschodnio-galicyjskiej, którą nabyto wcześniej za 900 zł poprzez losowanie za zniesienie pańszczyzny i dziesięciny kościelnej. Koszt budowy kościoła był za pewne sporym obciążeniem dla wspólnoty parafialnej, stąd też starano się wykorzystać znaczną część zarówno elementów konstrukcyjnych, jak i wyposażenia dawnej świątyni. Nad prezbiterium przeniesiono także starą wieżę na sygnaturkę. W 1878 roku Józef Pochwalski wykonał polichromię w prezbiterium. Nawa została pomalowana w 1885 roku przez F. Gluza i J. Kubisza. Konsekracja nowej świątyni miała miejsce 22 sierpnia 1889, a dokonał jej kardynał Albin Dunajewski, biskup krakowski, wówczas miała także miejsce wizytacja kanoniczna parafii. Obecny kształt zyskał dopiero w latach dwudziestych XX wieku, ponieważ w trakcie I wojny światowej zniszczeniu uległa wolnostojąca dzwonnica. Postanowiono ją odbudować w postaci przylegającej do bryły kościoła wieży. W 1928 roku pod chórem w obrębie dobudowanej wieży wykonana została betonowa posadzka. Prace nadzorował Bartłomiej Kowalczyk, miejscowy budowniczy kościołów (m.in. kościół Redemptorystów w Krakowie, sklepienie kościoła św. Józefa w krakowskim Podgórzu, kościół w Krzywaczce). W latach trzydziestych XX wieku ponownie pomalowano wnętrze kościoła. Prace zostały zlecone zakładowi malarskiemu Wymiatałków z Wieliczki, w 1934 roku przeprowadzono je w prezbiterium, natomiast 1936 roku w pozostałej części kościoła. Tuż po zakończeniu II wojny światowej, w 1946 roku wzniesione zostało wokół kościoła murowane ogrodzenie, w którym umieszczone zostały cegiełki z nazwiskami wszystkich ofiarodawców. Rok później do bryły kościoła dobudowany został babiniec. W 1956 roku założona została instalacja elektryczna oraz wymienione stare, drewniane tabernakulum. Szereg poważnych prac budowalnych przeprowadzono za probostwa księdza Jana Pałasza, a rozpoczęły się one w 1985 roku, kiedy pokryto blachą miedzianą dach kościoła oraz hełm wieży, który wówczas zmienił nieco swoją formę. W latach dziewięćdziesiątych XX wieku z okazji jubileuszu siedemsetlecia parafii został przeprowadzony szereg prac konserwatorskich, jakimi objęto wyposażenie kościoła, jak i jego bryłę m.in. zewnętrzne ściany pokryto deskami modrzewiowymi, wymieniono posadzkę prezbiterium, pod chórem oraz w zakrystii. Jesienią 1990 roku rozpoczęto konserwację polichromii, którą przeprowadzili Barbara Budziaszek i Wojciech Kurdziel.
Paulina Chełmecka, "Kościół Ducha Świętego w Podstolicach", [w:] "Sakralne Dziedzictwo Małopolski", 2024, źródło: https://sdm.upjp2.edu.pl/dziela/kosciol-ducha-swietego-w-podstolicach