År 1619 invigdes första kyrkan i Föllinge. Det var en träkyrka som låg på nästan samma plats som nuvarande kyrka. Den var mycket liten, 11 alnar lång (ca 6,5 meter) och hade sex bänkar på vardera sidan.
Prästen i Lit skulle hålla gudstjänst i Föllinge var fjärde helgdag. Övriga söndagar fick sockenborna från Föllinge åka till Lit. Eftersom det var så långt till kyrkan i Lit, och vägen bara var en gång- och ridväg, var Föllingeborna inte så flitiga kyrkobesökare. De blev därför ålagda att besöka kyrkan i Lit vid vissa högtider. Om de då inte kom till kyrkan blev de bestraffade.
Föllinge socken avskildes från Lit 1742 och blev ett eget pastorat. Men först 1746, när dåvarande kyrkoherden i Lit avled, anställdes kyrkoherden Olof Sebrelius (anställd 1746-62). Antalet kyrkobesökare ökade, kyrkan blev för liten och man byggde därför ut den. Ombyggnaden var klar år 1761. Kyrkan, som tidigare var 11 alnar lång, blev då 24 alnar lång och 15 alnar bred, det byggdes även en kupolstapel (klockstapel).
Sebrelius var den förste kyrkoherden i Jämtland med det officiella uppdraget att lokalt arbeta för samernas omvändelse och upplysning. När han år 1746 tillträdde sin tjänst i Föllinge pastorat fick han ansvaret för det kyrkliga arbetet bland den samiska befolkningen i hela Jämtland och Härjedalen. Ett väldigt stort område, dessutom vistades samerna ibland i Norge, vilket gjorde området ännu större. När den slutgiltiga gränsläggning mellan Jämtland/Härjedalen och Norge fastställs år 1751 blev samerna ålagda att välja vilket land de skulle tillhöra.
Birger Cederberg (kyrkoherde 1762-63) arbetade som lärare vid lappskolan i Föllinge från starten 1746. Han tog pastorsexamen år 1758 och vid Sebrelius avgång år 1762 anställdes han som pastor i Föllinge, samtidigt som han hade kvar skolmästartjänsten. Han odlade också samtidigt upp det torp han hade som tjänstebostad. Trots att han hade två tjänster hade han svårt att klara sig ekonomiskt och sökte sig söderöver. Han skriver i sin ansökan ”Jag har redan måst utur fjällbygden ned på landet, i brist på föda och nödigt uppehälle, afsända hustru och sju barn, och själf stadna vid mitt lilla torp, till thess Herren med hjälpen kommer”. Hans ansökan beviljades och hans ansökan om att bli befordrad och förflyttad beviljades.
Kyrkoherden Erik Jonas Ångman (anställd 1763-94) skriver i "Berättelse om Föllinge och Ström lappmarker" daterad 1768 att lapparna är flitiga att komma till kyrkan, delta i gudstjänsten och i förhör. Av de 240 lapparna inom Föllinge lappförsamling år 1767 kan över 100 vuxna läsa. Det stämmer med vad Lars Levi Laestadius noterade vid ett besök i Föllinge församling 1884. Han var utsedd att inspektera det kristna livet i skolor och församlingar i lappmarken, i Föllinge konstaterade han att samerna där visade större nit för kristendomen än svensken i genomsnitt.
Johan Axel Huss, (kyrkoherde från 1796 till 1820), ansåg att kyrkan, trots den tidigare utbyggnaden, var för liten. Han tog initiativ till ett nytt kyrkobygge, som genomfördes utan godkända ritningar och utan tillstånd. Den nya träkyrkan byggdes något öster om den gamla, som då revs. Föllinges andra kyrka invigdes 1815.
Foto: Föllinge kyrka före ombyggnaden 1885
I början av 1800-talet strålade tillfartsvägarna till kyrkbyn Föllinge samman i den så kallade Kilsvedjan, vid den fastighet som idag ligger på Axelåsvägen 10 (ägare Stig Andersson). Här byggde sig kyrkoherde Huss en prästgård. En stenlagd gång ledde genom huset och när hästskjutsar körde upp framför gården var det bara att stiga direkt in till prästen.
Prosten Carl Axel Rothoffs (anställd 1822-59) andra hustru räddade kyrkan från brand, då åskan sommaren 1839 slog ner och antände kyrktornet. Tack vare henne blev det bara mindre skador på kyrkan och det mesta gick att rädda.
1880-talet var en tid med kraftig befolkningstillväxt och under kyrkoherde Jonas Medins tid (anställd 1862-89) blev kyrkan föremål för en kraftig ombyggnad. Den förlängdes, fick ett nytt torn och återinvigdes 1885.
Efter pastor Medins död anställdes i Föllinge Carl Mikael Stenborg som präst (anställd 1892-1920). Hans hustru Theodora var mycket trädgårdsintresserad och det sägs att hon började gråta när hon fick se den karga och eländiga tomten vid prästgården i Föllinge. Hon anlade under åren som prästfru en vacker trädgård med perenner, buskar och träd.
Kyrkbyggnaden i Föllinge restaurerades 1950 och en invändig upprustning skedde 1978. Vid en brand den 17 juli 1994 totalförstördes kyrkan. En ny kyrka byggdes på samma plats, den invigdes fyra år efter branden.
Bild: Kyrkan 1952