Fella- og Hólakirkja er í Fella- og Hólaprestaköllum í Reykjavíkurprófastsdæmi eystra. Fellasöfnuður var stofnaður 1973 en Hólabrekkusöfnuður 1987. Fyrri áfangi kirkjunnar var vígður 24. marz 1985. Byggingarmeistari var Jón Hannesson.

Fellasókn var stofnuð í marz 1973.  Séra Lárus Halldórsson þjónaði í tvö ár í Fellaskóla.  Fellaprestakall var stofnað í febrúar 1975 og sr. Hreinn Hjartarson var skipaður sóknarprestur skömmu síðar og var falið að þjóna Hólahverfi líka.  Starf safnaðarins hélt áfram í Fellaskóla.  Vorið 1975 keypti söfnuðurinn Keilufell 1, þar sem presturinn, sóknarnefnd og aðrir, sem komu að starfi safnaðarins, fengu starfsaðstöðu.  Innrétting kapellu í safnaðarheimilinu hófst fljótlega og hún var vígð í desember 1976 ((herra Sigurbjörn Einarsson, biskup).  Ári síðar var salur kapellunnar stækkaður, þannig að rými varð nægilegt fyrir kór og orgel.  Jólin 1977 hófst þar guðsþjónustuhald, sem hélt áfram til ársins 1983

Árið 1987 var stofnuð ný sókn, Hólabrekkusókn, og hverfið var gert að sérstöku prestakalli.  Séra Guðmundur Karl Ágústsson var skipaður sóknarprestur.  Hann tók til starfa um haustið.  Í upphafi stóð til að byggja tvær kirkjur, aðra fyrir Hólabrekkusókn og hina fyrir Fellasókn.  Fallið var frá þeirri tilhögun og ákveðið að sameinast um eina kirkju fyrir báðar sóknirnar.

Heiðursmaðurinn Jón Hannesson, byggingarmeistari, var fenginn til að stjórna byggingarframkvæmdum.  Ingimundur Sveinsson og Gylfi Guðjónsson voru arkitektar kirkjunnar. Hún var byggð í áföngum og vígð formlega 1988.  Hún er mjög hagkvæm og hefur fengið háa einkunn fyrir gott aðgengi.  Öll salarkynni eru á sama gólfi, nema herbergi í kjallara, sem voru innréttuð síðar fyrir starfsemi sóknarnefndanna.  Þar er einnig aðstaða fyrir unglinga.

Þegar mikill mannfjöldi er í kirkjunni, er hægt að opna inn í safnaðarsalinn, sem er þannig staðsettur, að allir sjá þaðan inn í kór kirkjunnar.  Einkenni kirkjunnar er gluggabandið í kringum allt húsið og mikil jarðvegsfylling.  Tilfinning fólks fyrir kirkjunni átti að vera sú, að hún væri vel jarðbundin en gluggabandið skæri efri hlutann frá jörðu og gerði hann ójarðbundnari.  Í rökkri eða myrkri virðist efri hlutinn fljóta á jörðinni og bendi til himins.
Glerlistaverkin í kirkjunni eru eftir Leif Breiðfjörð.  Hin fyrstu þeirra voru sett upp árið 1997 og restin ári síðar.  Samtímis vinnslu glerlistaverkanna var Sigríði Jóhannsdóttur og Leifi falið að vinna allan skrúða fyrir kirkjuna.  Þau tóku mið af byggingarstíl kirkjunnar og litum í glerlistaverkunum við þá vinnu.