Ein reknar med at steinkyrkja er bygd ca. 1153. Ho er nemnd første gong i eit vernebrev frå pave Gregor IX i 1228.[3] Kyrkja er prostikyrkje i Fana prosti.
I 1723 vart kyrkjene i Noreg lagt ut for sal, og òg Fana kyrkje hamna på private hender. Det var to av velståande innbyggjarar i bygda som saman fekk tilslaget på 169 riksdalar og 12 skilling, desse var Nils Olson Austevoll og Vinsens Nilsson Nedre Titlestad.[4] Fyrst i 1862 vart kyrkja kjøpt tilbake av soknet. Nesten 150 år i privat eige hadde medført tydeleg forfall, og ein valde difor å gå gjennom ei omfattande ombygging som vart avslutta i 1871.[5] I denne samanhengen vart svært mykje av inventaret til kyrkja fjerna og auksjonert bort. Det meste av dette er i dag rekna som tapt. Det tok ikkje lang tid før ein innsåg at denne ombygginga var ein tabbe, og i 1920-åra vart arkitekten Fredrik Konow Lund rekvirert til å leie arbeidet med å tilbakeføre kyrkja til den opphavlege utforminga si som ho hadde hatt sidan mellomalderen.[6] Ytterlegare restaureringsarbeid vart gjorde i samband med kyrkja sitt 800-årsjubileum i 1953 der òg kong Haakon VII deltok.[7]
I nyare tid har kyrkja blitt restaurert både innvendig og utvendig, og det meste av arbeidet var fullført sommaren 2008. Blant anna er overflater vorte kalka og måla innvendig, og skifertaket er skifta ut.
Segna om den heilage sølvkrossen
Ifylgje ei gammal segn skal to brør, den eine av dei blind, ha fiska opp ein sølvkross utanfor Korsneset i Korsfjorden i Fana. Den blinde skal ha vorte lækt etter å ha rørt ved krossen.[8]
Så skal dei ha teke krossen til kyrkja, der det skal ha lækt sjuke som rørde ved det. Dei sjuke skal ha kasta frå seg krykkene på ein stad ved kyrkja som i dag heiter Krykkjehaugen.[2] Det er sagt at presten Peder Simenssen i 1546 skal ha brunne seks hestelass med krykker og stavar frå denne staden. I mellomalderen var Fana kyrkje eit pilegrimsmål, og det låg òg eit hospital ved kyrkja. I vernebrevet frå pave Gregor IX er kyrkja omtalt som kyrkja til den heilage krossen.