Skrzydlna jest jedną z najstarszych miejscowości w powiecie limanowskim – według tradycji to właśnie tędy szedł do Prus w końcu X w. św. Wojciech. Kościół w Skrzydlnej jest fundacją rycerską, parafia pierwotnie obejmowała okoliczne majątki należące do rodu Szarzów. Przypuszcza się, iż została ona wydzielona z sąsiedniej parafii w 1296 r., w wyniku sporu Ratołda h. Szarza z cystersami o prawo patronatu do kościoła w Szczyrzycu.
Pierwsza wzmianka o parafii pochodzi z 1326 r., kiedy to Mikołaj, pleban ze Skrzydlnej (Nicolao, plebano de Cridlna seu Antiquo Rudel) opłacił za lata 1325-26 dziesięcinę papieską. Z 1325 r. lub z 1335 r. pochodzi dokument w sprawie lokacji wsi Dębno na Podhalu, gdzie świadkiem był również Mikołaj, pleban ze Skrzydlnej. Falsyfikatem z końca XVIII w. jest natomiast pergaminowy dokument przechowywany w Archiwum Diecezjalnym w Tarnowie, wg którego parafię miał ufundować w 1315 r. hetman Petrazjusz Janina.
Murowano-drewniany kościół filialny (dawniej parafialny) w swoim obecnym kształcie sięga prawdopodobnie z 1424 r., kiedy to król Władysław Jagiełło wyraził zgodę na lokację miasta Skrzydlna na prawie niemieckim. Wtedy to wytyczono plac targowy, w którego północno-wschodnim rogu znajdowała się świątynia. Choć przeprowadzone w 2019 r. badania zapraw metodą 14C wskazują, że murowane prezbiterium, a co za tym idzie kamienna mensa ołtarza głównego oraz najstarsza warstwa posadzki, pochodzą z końca XIV w. Z kolei badania dendrochronologiczne drewnianej części kościoła potwierdziły jednoznacznie, że nawa powstała w okresie lokacji miasta Skrzydlna, co czyni skrzydlański kościół jednym z najstarszych drewnianych zabytków w Małopolsce. Za nieprecyzyjny należy natomiast uznać zapis Jana Długosza w Księdze uposażeń diecezji krakowskiej z lat 1470-80, który kościół w Skrzydlnej opisał jako drewniany, pomijając murowane prezbiterium.
Na początku XVI w. Skrzydlna przeszła w ręce rodziny Pieniążków h. Odrowąż, wtedy też przebudowano kościół w stylu gotycko-renesansowym. Śladami przebudowy są: druga warstwa posadzki, najstarsza zachowana polichromia pokrywająca ściany prezbiterium i nawy (wykonana przez malarza Jana z Lipnicy w 1517 r.), a także późnogotycki portal w ścianie północnej prezbiterium wraz z murowaną zakrystią. Ok. 1520 r. powstał też tablicowy obraz z przedstawieniem Matki Boskiej, św. Stanisława Biskupa i św. Mikołaja, skradziony w 1999 r. i dotąd nie odzyskany. Z XVI w. pochodzi ponadto kamienne ścienne sakrarium (z ok. 1540 r.) oraz nagrobek Prokopa Pieniążka, wykonany prawdopodobnie w 1567 r. przez Hieronima Canavesiego – nadwornego rzeźbiarza króla Zygmunta Augusta. Zgodnie z protokołem wizytacji biskupiej z 1596 r. kościół (konsekrowany) był wówczas budowlą murowano-drewnianą z wieżą, obok znajdował się też cmentarz z kostnicą. We wnętrzu odnotowano 6 niekonsekrowanych ołtarzy, których konsekracji dokonał dopiero w 1621 r. biskup Tomasz Oborski.
Przebudowa świątyni w stylu barokowym miała miejsce pod koniec XVII, kiedy to nadano budowli jej obecny kształt. W całym kościele wprowadzono wówczas sklepienie pozorne. Na początku XVIII w. wykonano też nowe, barokowe wyposażenie świątyni, w tym nastawy ołtarzowe z obrazami i rzeźbami, ambonę i chrzcielnicę. Ściany kościoła pokryła zaś barokowa polichromia – zachowana fragmentarycznie na ścianach prezbiterium i szczątkowo na drewnianych stropach.
W późniejszym okresie kościół wielokrotnie remontowano, w tym m.in. przebudowywano obciążoną ciężkimi dzwonami wieżę, którą z czasem przykryto blaszanym hełmem. Ok. 1800 r. zdemontowano kaplicę północną, natomiast w 1880 r. do nawy dobudowano kaplicę południową. W 1910 r. dach kościoła pokryto blachą cynkową. W trakcie remontu w latach 1928-1930 poszerzono chór muzyczny i zakupiono nowe organy.
W latach 1999-2002 miała miejsce seria kradzieży w starym kościele, w wyniku których utracono większości obrazów, rzeźb i innych sprzętów ruchomych. Od kilku lat trwają interdyscyplinarne prace konserwatorskie, dzięki którym udało się zasadniczo zweryfikować dotychczasową wiedzę o tym cennym zabytku.
