Znalazł już nawet plac przeznaczony pod budowę świątyni, lecz władze komunistyczne wybudowały tam karczmę, która później spłonęła.
W końcu udało się uzyskać zezwolenie na budowę, wydał je wojewoda sądecki w 1975. W 1978 plac przeznaczony pod budowę poświęcił ks. bp Jerzy Ablewicz, a rok później powstały pierwsze fundamenty. 22 czerwca 1980 do Sowlin przybył ponownie ks. bp w celu wmurowania kamienia węgielnego, poświęconego przez Jana Pawła II w Nowym Targu.
Początkowo trwała budowa dolnego kościoła. Już po 4 latach mógł być on używany przez wiernych. Poświęcenia w 1984 dokonał pochodzący z Limanowej ks. bp Piotr Bednarczyk. Teraz wierni mieli dużo lepsze warunki, lecz kościół czekało jeszcze 9 lat budowy. Dzięki oddanej pracy także mieszkańców parafii budowę ukończono w 1993, a konsekracji świątyni dokonał 16 maja ówczesny biskup tarnowski Józef Życiński.
Kościół nie został jednak nigdy całkowicie wykończony. Do 2002 budynek nie posiadał żadnej wieży, a dzwony wisiały na placu przed świątynią. W 2002 ukończono wieżę przeznaczoną na sygnaturkę, a 2 lata później największą więżę, w której obecnie wiszą dzwony.