Kyrkan i Fredrika är en rektangulär långhuskyrka i panelat liggtimmer med valmat mansardtak och ett smalare rakslutet kor. Kyrkan som uppfördes 1796–97 av fyrtio bönder i kapellaget under ledning av Erik Eriksson från Holmträsk i Åsele, är ett av de tidigaste exemplen på nyklassicistisk kyrkoarkitektur i Övre Norrland. Ursprungligen var kyrkan rödfärgad men erhöll ny vitmålad panel 1873, vilket onekligen ytterligare bidrog till den nyklassicistiska karaktären.
Vid kyrkorummets östvägg fanns ursprungligen en altarpredikstol, tillverkad av församlingens förste kyrkoherde, Jonas Ångman.
Predikstolen inramades av en draperimålning utförd av målarmästaren Jöns Asplund från Ström i Jämtland. I samband med en restaurering 1877 övermålades Asplunds verk.
I början av 1930-talet utfördes en genomgripande renovering av hela kyrkan. Bland annat gjordes sakristian om till kor, varvid predikstolen flyttades till en, inom Svenska kyrkan vanligare position vid rummets norra vägg. Denna förändring innebar att en stor öppning upptogs i den ursprungliga korväggen, där alltså Asplunds målning låg gömd under lager av färg. Vid en restaurering på sextiotalet under ledning av Bengt Lidström framtogs och konserverades det som fanns kvar av målningen.