Historia parafii w Zahutyniu rozpoczyna się w 1979 r., lecz zanim doszło do założenia parafii, na tych terenach toczyło się życie miejscowych, katolików.
Zahutyń- choć to wieś nader stara, kościół ma całkiem nowy. Wierni obrządku wschodniego modlili się we własnej cerkwi, natomiast rzymsko- katolicy należeli do parafii sanockiej. W 1869 roku wiernych obrządek łaciński wyznawało w Zahutyniu 32 osoby, natomiast w 1914 roku 80 osób.
Po II wojnie światowej Zahutyń pozbawiony był świątyni przez 11 lat. Księża z parafii rzymsko-katolickiej Najświętszego Serca Jezusowego w Sanoku dojeżdżali do Zahutynia i odprawiali msze raz w miesiącu, w budynku szkolnym.
W 1956 roku mieszkańcy Zahutynia, prześladowani przez ówczesne władze polityczne uzyskali wreszcie pozwolenie na budowę kaplicy przedpogrzebowej. Powołano komitet budowy.
Wierni wykorzystali wolny plac po byłej cerkwi i wznieśli na nim drewniany kościółek pod wezwaniem Najświętszej Marii Panny Królowej Polski. Budowla ma konstrukcję wieńcową z szerszą od nawy kruchtą po północnej, i prezbiterium po południowej stronie. Ściany oszalowane są deskami i ze wzmocnione z lisicami.
Na początku z uwagi na trudności w zdobyciu innego materiału dach kościoła pokryty został papą. Przy prezbiterium była zakrystia, a z drugiej strony magazynek na rzeczy związane z kultem. Strop kościoła był kasetonowy.
Pod koniec lat sześćdziesiątych, gdy proboszczem w parafii NSJ w Sanoku był ks. Kazimierz Pyś, rozpoczęto prace przy wykończeniu kościoła. Oszalowano i zakonserwowano całe wnętrze kościoła, wykończono chór, a dach pokryto blachą. Ogrodzono siatką całą parcelę, łącznie z cmentarzem. Wykonano betonowe fundamenty pod kościołem, bo początkowo kościół stał na prowizorycznej podmurówce. Położono również posadzkę ceramiczną w całym kościele.
Kościół dostosowano również do odnowionej liturgii, a więc wykonano nowy ołtarz i ambonkę. Obok prezbiterium umieszczono figury Pana Jezusa i Matki Bożej, na chórze fisharmonię, zaś na ołtarzu nowe, metalowe tabernakulum, wykonane przez Juliana Opryszkę z Przemyśla. W roku 1976 zbudowano drewnianą dzwonnicę, w której umieszczono sygnaturkę i dzwon, podarowane przez parafię Najświętszego Serca Jezusowego w Sanoku Kościół w Zahutyniu pod wezwaniem Matki Bożej Królowej Polski poświęcił 8 maja 1978 r. ks. bp Tadeusz Błaszkiewicz.
Sanoccy księża z parafii NSJ w Sanoku odprawiali msze św. w Zahutyniu do 1979 roku. 2 sierpnia tegoż roku ordynariusz przemyski ks. biskup Ignacy Tokarczuk odłączył Zahutyń i Dolinę od parafii NSJ w Sanoku i utworzył nową parafię w Zahutyniu. Parafia objęła Zahutyń i Dolinę, zamieszkałe przez 1400 wiernych.
Pierwszym proboszczem oraz przełożonym klasztoru był o. Walenty Miklaszewski, który objął placówkę 7 sierpnia 1979 roku. Prowincjałem zakonu był wówczas o. Alfons Kupka. Ojcowie zamieszkali najpierw w prywatnym domu. Zaraz też pomyślano o budowie klasztoru. Mimo trudności z tym związanych, 19 grudnia 1981 roku ojcowie przeprowadzili się do nowego, jeszcze niewykończonego budynku klasztornego. Kolejnymi proboszczami byli: o. Leon Witek, o. Stefan Kruk, o. Czesław Pantoł, o. Czesław Motak, o. Edward Ruszel, a od 1 lipca 2011 roku o. Adam Jaworski.
Kościół w Zahutyniu stan obecny Z inicjatywy Rady Parafialnej jak również całej wspólnoty, kościół został powiększony o 6 m długości i 3 m szerokości. Plan rozbudowy kościoła opracowała inż. Maria Winnik z Sanoka. Wszystkie prace nadzorował ówczesny proboszcz ks. Czesław Pantoł. Dobudowaną część kościoła uroczyście poświęcił w dniu 20 maja 1997 roku, z okazji wizytacji parafii Zahutyń, ks. Arcybiskup Metropolita Przemyski Józef Michalik.
Parafia Zahutyń istnieje od 1979 r. Liczy około 1300 wiernych, obejmując Zahutyń i Dolinę. Dnia 2 lipca 2006 roku nastąpiła konsekracja ołtarza wykonanego z kamienia, ambonki oraz prezbiterium. W kamiennym ołtarzu spoczną relikwie świętego Józefa Sebastiana Pelczara. Projekt nowego wystroju ołtarza głównego wykonany został przez mgr inż. Mariolę Sidor.
W nowym kościele nie ma zabytkowych elementów. Jedynym cennym elementem jego wystroju jest XVII-wieczny, malowany na desce, obraz Matki Boskiej Szkaplerznej w drewnianych sukienkach, przeniesiony końcem maja 1956 roku do Zahutynia z klasztoru oo. franciszkanów w Sanoku.
Obraz ten prawdopodobnie pochodzi z zagórskiego klasztoru karmelitów bosych po tragicznym pożarze w 1822 roku, który zniszczył kościół i klasztor. Uratowane z pożogi obrazy przeniesiono do kościoła parafialnego w Zagórzu, a stamtąd do innych świątyń. Dziś obrazy znajdują się m.in. w kościołach w Tarnawie Górnej i Zagórzu.
Prawdopodobnie i ten w Zahutyniu, bo brak jest jakichkolwiek dokumentów pochodzenia tego cudownego obrazu. W 1888 roku ołtarze w kościele franciszkańskim, w tym i obraz Matki Boskiej Szkaplerznej był restaurowany przez firmę Majerskiego. Z kolejnego zapisu dowiadujemy się, że w grudniu 1936 roku obraz MB Szkaplerznej poddano odnowieniu. Odnowienia ołtarza i obrazu dokonał sanocki malarz Władysław Lisowski.
Już w Zahutyniu obraz MB Szkaplerznej poddano gruntownej renowacji. Dokonał jej w roku 1976 konserwator wysokiej klasy – dr Wojciech Kurpik. Podczas renowacji okazało się, że na desce malowane są tylko twarze, a cała sukienka jest z tektury, dawniej prawdopodobnie była z blachy srebrnej. Konserwator wykonał sukienkę z drewna lipowego i pokrył ją metalowymi złotymi płytkami z odpowiednim lazerunkiem.
W 2000 roku obraz poddano kolejnej renowacji i pozłocono. Dwa lata później został ozdobiony bogatym ornamentem. Na koniec 2005 roku Zahutyń liczył 1085 mieszkańców.
W roku 2011 dokonano oczyszczenie i pomalowania zewnętrznej elewacji kościoła, w roku 2012 oczyszczono i pomalowano blachę na świątyni, dzwonnicy i budynku gospodarczym. W roku 2013 wymienione zostały okna w nawie głównej na aluminiowe i zamontowano w nich witraże. Witraże przedstawiają: Matkę Bożą Królową Polski, św. Jana Pawła II, św. Floriana, św. Eugeniusza de Mazenoda i ostatni z pejzażem bieszczadzkim przedstawiającym Krzyż na Tarnicy.
Pod koniec 2013 roku ocieplony został strych w kościele, oraz wykonano prace wzmacniające konstrukcję dachu. W roku 2014 na cmentarzu zrobione zostały nowe schody oraz wykonana została alejka. Prace te znacznie polepszyły możliwość poruszania się po nekropolii, a jednocześnie sprawiły, że parafialny cmentarz jest jeszcze bardziej zadbany.