Původní kostel sv. Mikuláše, biskupa Myrenského, byl dřevěný a poprvé byl zmíněn již v roce 1350 jako filiální do Ždánic, což potvrzuje též Josef Sakař ve svých několikadílných "Dějinách Pardubic nad Labem". Původně patřil stejně jako ves sedleckému klášteru, který vznikl kolem roku 1142. Do roku 1421 náležel opatovickým benediktinům (v roce 1358 po smrti ždánického plebána Diviše byl podán opatem Neplachem jako jeho nástupce kněz Mikuláš) a od roku 1436 měl podací právo Diviš Bořek z Miletínka a od roku 1509 Vilém z Pernštejna. Podle lidových podání však stával na jiném místě, a to tam, kde u křižovatky stávala kamenná kaplička s klekátkem, do níž 10. července 2022 narazila dodávka a úplně ji zničila (viz
https://www.idnes.cz/pardubice/zpravy/nehoda-automobil-kaplicka-umrti-ridic-lazne-bohdanec.A220710_212954_pardubice-zpravy_lisv?). V roce 1565 tvořilo jeho příjmy 14 kop, 28 grošů a 5 denárů a 4 zádušní krávy (za každou bývalo dáváno po 1 libře vosku nebo 14 grošů platu). Vydání ve výši 25 kop, 8 grošů a 1 denár však byla větší, protože se opravovala zvonice, a tak muselo dojít k zápůjčce od Vavřince Machuty z Podůlšan.
Nový kostel vznikl koncem 17. století, aniž bychom znali osudy jeho předchůdce. O jeho vzniku vypovídají vizitační zprávy církevní z roku 1677, kdy byly Ždánice a Podůlšany filiálními do Osic. Podle nich 28. září 1664 položil základ tohoto svatostánku osický farář P. Jiří Kryštof Hájek, který byl do roku 1654 pardubickým děkanem a ovládal i ždánickou kolaturu s podůlšanskou filiálkou. Postaven byl nákladem jednoho rolníka hospodařícího na gruntě vinařovském a k jeho dokončení došlo v roce 1665, což dokládal též nápis na jednom dřevěném sloupu: „Anno Domini 1665“. Původně však byl chrám veden pouze jako kaple, jež měla roku 1677 1 stříbrný kalich, 1 stříbrnou pušku, nově zaopatřenou mosaznou monstranci (starší mosazná a pozlacená monstrance byla před lety dána do Sezemic), 10 cínových svícnů a 3 zvony na nové věži.
Jeho presbytář byl tvořen nepravidelným pětistěnem a loď měla obdélníkový půdorys. Strop byl prkenný a trámovitý. Hlavní oltář sv. Mikuláše byl zdoben sochou téhož světce a na stranách byly umístěny sochy sv. Vojtěcha a sv. Václava. Kamenný oltářní stůl měl na sobě německý nápis a podle všeho byl původně náhrobním kamenem. Oltářní kámen, který se nacházel uprostřed, sloužil k uchování ostatků sv. Floriána a Saturnina. Posvěcen byl 15. října 1692 Mons. Josefem Curtiem Žibokou, biskupem suffraganem pražským. Nad sochou sv. Mikuláše byl umístěn sv. Kříž. Postranní oltáře Panny Marie a sv. Anny byly z pozdější doby, a tudíž historicky bezcenné. Jen oltářní kámen prvně zmíněného oltáře měl ostatky sv. Placida, sv. Konstancia a sv. Šebestiána a k jeho posvěcení biskupem Mons. Janem Novostatským došlo 15. června 1650. V sakristii za oltářem byl ukryt misál, který byl zakoupen pro potřeby osického záduší v roce 1638 pardubickým farářem p. Jiřím Stoloniem. Střecha byla šindelová a místo římsy byly na konci střechy vazební trámy zapuštěné do zdi, okna byla nízká, malá a podlouhlá. Presbytář byl nižší než chrámová loď. Ve zvonici nad vchodem se nacházela trojice zvonů. Větší nesl nápis: „Tento zwon slyt gest ode mnie Martina Exnera zwonarze w miestě Kralowom Hradczi nad Labem. Nakladem Podulssanskeho za sprawcze Salomona Machuty toho czasu rychtarze a Ondrzege Horcziczky kostelnika ke czti a chwale Panu Bohu wssemohuczimu.“ Menší zvon z 15. nebo 16. století měl na sobě text: „Ave Maria gracia plena dominus tecum benedicta tu in mulieribus et benedictus fructus ventris tui“, neboli - „Zdrávas Maria milostiplná, Pán s Tebou, požehnaná Ty jsi mezi ženami“. Třetí zvonek byl roku 1841 ukraden.
Později byl kostel kvůli sešlosti uzavřen (v polovině roku 1888) a 5 let v něm žádné bohoslužby neprobíhaly. Následně byl určen k zbourání. Díky ochotě obecního zastupitelstva byl rozebrán roku 1894 a zejména jeho vnitřek a šindel obzvlášť využit na kostelík, který byl navržen architektem Eduardem Sochorem pro Národopisnou výstavu českoslovanskou v Praze v roce 1895. Tentýž člověk si vymohl úřední povolení, aby mohl pořádat sbírky ve prospěch znovupostavení téže svatyně v Podůlšanech. Krátce nato se začalo přemýšlet o tom, jak by měl nový svatostánek vypadat a kdo by ho měl navrhnout a postavit. 8. června 1898 navíc obecní starosta Antonín Rychter a radní František Vinař písemně žádali Zemský výbor království Českého, aby se zasadil o navrácení inventáře, který byl použit na výstavě (3 oltáře, kazatelna, svícny, korouhve, obrazy, sochy, celý chór s varhany, 16 lavic, 2 kropenky, velké železem pobité dveře a 2 zvony) a nebyl obci dosud navrácen, jak předpokládala smlouva ze 4. ledna 1895. Krátce poté byla věc vyřízena.
Poté se již obec začala věnovat výstavbě nového svatostánku. Původně se obecní zastupitelstvo rozhodlo pro to, aby byl kostel navržen architektem Františkem Schmoranzem. Stalo se tak v květnu 1900. Nelíbilo se mu však to, že věž byla v jeho plánech umístěna vzadu, následně byly rozporovány i další detaily. Architekt ve všem ustoupil a v říjnu téhož roku došlo s drobnými výhradami k povolení stavby c. k. okresním hejtmanstvím, načež však obec opět změnila názor. Počátkem následujícího roku se tak objevily 2 plány od pardubického architekta Josefa Krudence, přičemž první byl inspirován gotikou a ten druhý románským slohem. Oba plány však následně dopadly stejně jako návrhy Františka Schmoranze. Nakonec byl vybrán projekt od kolínského stavitele Čeňka Křičky a stavbou byl pověřen zednický mistr Josef Hroch z Praskačky, který ji dokončil roku 1903 (podle knihy "Edice nedokončeného soupisu uměleckých památek politického okresu pardubicko-holicko-přeloučského" od Václava Karla Vendla, kterou vydala a editovala v roce 2007 Jana Marešová, měl kostel stavět pardubický architekt Boža Dvořák, ale jde o omyl, čehož důkazem může být i poděkování za slavnostní vysvěcení nového chrámu Páně, které schválili podůlšanští obecní zastupitelé). 13. září téhož roku došlo k slavnostnímu vysvěcení tohoto svatostánku královéhradeckým kanovníkem ThDr. Janem Nepomukem Soukupem, přičemž krásná okna z malovaného skla s obrazy dodala firma „Umělecký ústav pro malbu na skle B. Škarda, Brno“. Dnes je tento svatostánek filiálním do Opatovic nad Labem.
Tato jednolodní stavba s věží v průčelí se stala okamžitě dominantou obce, jež je již z dálky snadno identifikovatelná díky svému netypickému zakončení věže kopulkou na osmibokém půdoryse. Loď má délku 12,5 m a šířku 8,4 m; presbytář je dlouhý 4,7 m a široký 5,33 m a předsíň má délku 2,4 m a šířku 2,5 m. Vpravo je navíc sakristie o délce 3,58 m a šířce 2,15 m.
Interiér kostela je poměrně prostý. Zařízení pochází většinou z konce 17. století a bylo součástí inventáře původního dřevěného kostela. Interiéru dominuje barokní oltář s novým obrazem sv. Jana Nepomuckého a starou dřevěnou plastikou sv. Mikuláše o výšce 2,3 m, na stranách s 1 m vysokými sochami sv. Petra a Pavla a dole se stejně vysokými plastikami sv. Mikuláše a Václava. Jeho oltářní menza nese nápis: "Anno 1692 die 15. Octb. Illustrissimus ac Reverendissimus Josephus Kurtius in Zibok Sanctae et Apostolicae Sedis gratia Episcopus Sebastianus ac Suffraganeus Pragensis consecravit hoc altare portatile in honorem Dei omnipotentis, Beatae Mariae Virg. et OO. SS. specialiter vero in honorem SS. Martyrum Floriani et Saturnini, quorum Reliquias in eo inclusit." Vlevo je pak situován 1 m vysoký kříž. Nalevo se nachází boční oltář sv. Jana Křtitele, bohatší je však na opačné straně situovaný oltář Panny Marie se sochami sv. Kateřiny, sv. Julie a sv. Prokopa a oltářní menzou s textem: "Anno 1650 die 15. Junii Illustrissimus ac Reverendissimus DD. Joannes Neostadensis consecravit hoc altare portatile et Reliquias S. Placidi, Constantii et Sebestiani in eo inclusit." Do zadní stěny oltářní menzy je vsazen kamenný náhrobník s gotickým nápisem. Na konzolách presbytáře jsou umístěny sochy sv. Vojtěcha, sv. Václava, Panny Marie, sv. Anny, sv. Jiří a sv. Martina. Pod kruchtou je umístěna dvojice deskových obrazů světic z 1. poloviny 17. století, jež dříve byly nejspíše součástí deskového oltáře a teprve později byly zasazeny do osmibokých rámů. Nemuselo tomu však být, protože do kostela se vloupali zloději. Bylo štěstí, že odcizené plastiky byly v rámci policejní akce „Kříž“ objeveny a do kostela navráceny v roce 2000. Původní varhany pocházely z roku 1833 od neznámého varhanáře (varhany však byly v podůlšanském chrámu zmíněny již v roce 1721), nové byly zřízeny v roce 1902 od Antonína Mölzera z Kutné Hory.
Kolik je dnes ve věži zvonů, tak to nemohu sloužit, protože jsem se do věže nedostal. Nejspíše jen ten nejstarší, protože jsem našel zmínku o tom, že roku 1950 byl 1 zvon z Podůlšan přenesen do kostela sv. Jiří v Kostelci nad Orlicí a v roce 1963 byl umístěn v kostele sv. Kateřiny v Kačerově.