Fedje kirke

Korhuset

Den første kirken på Fedje ble bygget i 1659. Før den tid hadde det stått et korhus, trolig der kirken står i dag. Fedje hørte da til Lindås kirkesogn og sogneprest her i 1636 var Lytich Hansen Ovenstad. Han nevnte korhuset for første gang dette året og omtalte det som «æld gammelt» og at det var mer likt «et fæhuus» enn en kirke. Alterringen skal ha gitt rom for fem-seks mennesker om de knelte tett rundt presten, og nattverden måtte han dele ut «med indkorted Arm», fordi det var så trangt om plassen. Den siste gudstjenesten i dette korhuset ble holdt 24. april 1659, tredje søndag etter påske, før det ble revet.

Den første kirken

I 1657 reiste den bergenske skipperen Anders Bastiansen fra Finnmark og hjemover forbi Fedje da han ble truffet av et kraftig uvær. Han ba til Gud og ga løfte om at hvis han bare kom seg helberget til land skulle han gi en pengegave til kirken på dette stedet. Dette ble Fedje og for pengene ble korhuset revet og en ny tømmerkirke bygget på samme stedet. Korhuset ble revet i april 1659, men allerede 21. august samme år ble den nye kirken vigslet. Kirken var ikke så veldig mye større enn korhuset, og langskipet var bare 8 meter langt. 
Bastiansen finansierte ikke kirken alene, men fikk med seg flere menn fra Bergen, samt folk fra Fedje. Flere ga gaver til kirken som i dag finnes i den nåværende kirken. Dette var blant annet en sølvdisk, et stort oljemaleri fra 1661 som i dag henger i våpenhuset, og døpefat fra 1663.
Ifølge folkefortellingene stod ikke denne kirken der kirken i dag står, men på en holme nord for hovedøya kalt Helsøya, fordi det var her Bastiansen visstnok drev i land. På holmen ligger en steinrøys der man mener å kunne se konturene av en grunnmur. Rundt holmen finnes også flere lokale stedsnavn som Påskeflua, Koften (der presteskyssen en gang rant på land og presten mistet prestekjolen sin) og Brurebenken. Historiene regnes imidlertid som lite sannsynlige og kirken lå trolig på samme sted som den nåværende kirken.  
Fedje fikk kirkegård i 1679. Den samme Bastiansen var blant mennene som gjorde opptaket til at Fedje skulle få egen kirkegård, og kirkegården ble vigslet av tidligere nevnte sogneprest Ovenstad 23. april dette året. Før den tid måtte de døde føres over Fedjefjorden til Austrheim, en ferd som var strevsom og ofte farefull. Det var heller ikke egen prest på Fedje, prestene måtte skysses med robåt fra Lindås. Ofte ble preknene avlyste på grunn av dårlig vær ettersom presten ikke kom seg over fjorden. På 1800-talet var kirken i dårlig stand og eieren av kirken, Kahrs, søkte om å få rive kirketårnet så ikke vinden skulle ta det. Det er også noen som mener at Kahrs bygget en ny kirke en gang på 1800-talet, men det finnes ikke historiske kilder som viser dette bortsett fra en kallsbok der det står skrevet om kirken «En vakker liden Træbygning, som opførtes av dens forrige eier major Chr. Karhs». Den gamle kirken kan kanskje bare ha blitt restaurert i stedet. Uansett ble kirken på Fedje revet i 1888 for å gi plass til en ny. De gamle byggematerialene ble benyttet i et handelshus som stod på Stenborg på Fedje.

Den andre kirken

Den gamle kirken ble revet i 1888 og en liten trekirke ble vigslet av biskop Hvoslef den 17. oktober samme år. Skipet i denne kirken var 10,3 meter langt og 7,3 meter bredt med plass til om lag 80 mennesker. kirken hadde ikke orgel. I 1930 fikk kirken ny altertavle, en gave fra utflyttede norskamerikanere fra Fedje. Altertavlen er malt av Vilhelm Bjørknes fra Byrknesøy i Gulen kommune, mens treverket ble bygget i ledige stunder av en fyrvokter på Hellisøy fyr.  Denne altertavlen står i dag i den nåværende kirken.

Den nåværende kirken

Kirken fra 1888 ble raskt for liten og allerede i 1918 startet man å planlegge finansieringen av en ny og større kirke. Dette året ble det lagt ut lister der folk kunne skrive seg opp og gi gaver for å finansiere byggingen. I 1939 ble kirken fra 1888 revet. Starten av andre verdenskrig gjorde byggeprossesen vanskelig. Det kom påbud og forbud i tur og orden, samt rasjoneringer på byggematerialer. Det tok derfor tid å anskaffe materialer og få de tillatelster man trengte av tyskerne for å få kirken ferdig. Blant annet nektet den tyske okkupasjonsmakten å tekke tårnet med kobber, men det ordnet seg til slutt. I 1941 stod kirken ferdig og 7. september 1941 ble den vigslet av biskop Andreas Fleischer. 
Kirken er bygt i murstein, som passer bedre enn tremateriale til det barske havklimaet på Fedje. Taket består av Alta-skifer og tårnet er tekket med kobber.
I 1979 fikk kirken nytt orgel fra W. E. B. Orgelbau i Dresden i Tyskland med 16 stemmer.