Wieś istnieje od XVII wieku. Brak jednak danych o jej początkach. Nazwa Nawsie pojawiła się dopiero w 1772 r. Do czasu utworzenia parafii w Nawsiu w 1983 r. mieszkańcy korzystali z posługi duszpasterskiej kapłanów z Wielopola Skrzyńskiego. W latach 70. XX wieku pojawiły się jednak propozycje utworzenia samodzielnej parafii w Nawsiu i w konsekwencji wybudowanie własnego kościoła parafialnego. Pierwsze kroki ku temu poczyniono w 1972 r., kiedy pod kierunkiem ks. Franciszka Motyki - wikariusza z Wielopola przystąpiono do budowy kaplicy katechetyczno-kultowej. Ze względu na niesprzyjający czas budowano tę kaplicę jako prywatny dom Tomasza Łuszcza. Pomimo trzykrotnego przerywania prac przez władze, nauczanie religii rozpoczęto w tym budynku już w 1977 r. W kaplicy mieściła się także pierwsza plebania. Odprawianie Mszy św. w niedzielę i święta w kaplicy rozpoczęto w 1980 r. Już w 1982 r. rektorem kaplicy został ks. Stanisław Kos, wikariusz z Wielopola Skrzyńskiego, który podjął starania o utworzenie parafii i budowę kościoła.
Podczas pierwszego odpustu 15 maja 1983 r. ks. Julian Śmietana, proboszcz z Wielopola Skrzyńskiego odczytał akt erekcyjny parafii oraz nominację pierwszego proboszcza, którym został ks. Stanisław Kos.
Dzięki ofiarności nawsian udało się przygotować plac pod budowę kościoła. 10 lipca 1983 r. bp Jerzy Ablewicz poświęcił plac pod budowę świątyni. Budowa, dzięki zaradności ks. Kosa i zaangażowania parafian, szła bardzo dobrze. 19 maja 1986 r. podczas wizyty bp. Władysława Bobowskiego dokonano wmurowania kamienia węgielnego, poświęconego przez Jana Pawła II na Błoniach Krakowskich 22 czerwca 1983 r. Wmurowano także relikwie Ziemi z Katakumb św. Kaliksta w Rzymie. W następnym roku, 27 września 1987, bp J. Ablewicz ofiarował dla parafii relikwie bł. Karoliny Kózka.
Uroczystym zwieńczeniem wysiłków parafian z Nawsia przy budowie kościoła było jego poświęcenie, które miało miejsce 14 czerwca 1992 r. Należy zaznaczyć, że kościół w Nawsiu był poświęcony jako pierwszy w nowej diecezji rzeszowskiej, przez bp. Kazimierza Górnego, pierwszego ordynariusza rzeszowskiego.
Kościół zbudowany jest na planie krzyża greckiego według projektu inż. Władysława Boczkaja z Rzeszowa. Świątynia jest jednonawowa z boczną kaplicą po prawej stronie. Po przeciwnej stronie kaplicy znajdują się dwie zakrystie. Kościół posiada także przestronny chór. Krzyż w prezbiterium, jak również drzwi wejściowe, chrzcielnica i wiele innych drewnianych elementów, jest autorstwa miejscowego artysty rzeźbiarza Władysława Kuta.
Od początku istnienia parafii mieszkanie proboszcza mieściło się w kaplicy. Dopiero w maju 1997 r. ks. Marek Kiełbasa podjął się budowy plebanii w pobliżu kościoła. Budynek ukończono końcem października 1999 r. W 2004 r. wykonano elewację budynku plebanii oraz budynku pomocniczego, wybudowanego w 1998 r.
Wraz z powstaniem parafii podjęto starania o cmentarz. Po ofiarowaniu pola na ten cel oraz wykonaniu badań geologicznych plac pod budowę cmentarza poświęcił 21 października 1984 r. ks. dr Adam Nowak z Tarnowa.
Przez okres 25 lat istnienia parafia miała trzech proboszczów: ks. Stanisława Kosa (1983-94), ks. Marka Kiełbasę (1994-2001) oraz obecnie ks. Ryszarda Miśniaka (od 2001).
Godnym uwagi jest również fakt dużej ilości powołań. Z parafii pochodzi 6 kapłanów, 1 brat zakonny i 16 sióstr zakonnych.
Jubileusz ten jest okazją do dziękczynienia Panu Bogu za wszelkie dobro, które wynikło w czasie istnienia tej parafii, jak również kapłanom, którzy w niej pracowali. Dla nich, jak również dla wszystkich parafian należą się życzenia kolejnych pięknych rocznic.

Uroczystości jubileuszowe z udziałem bp. Kazimierza Górnego odbędą się w Nawsiu 17 maja br.