Í Efra-Breiðholti var stofnaður söfnuður, Fellasókn, árið 1973. Sóknarprestur Breiðholtssóknar, sem þá var sr. Lárus Halldórsson var settur prestur safnaðarins í byrjun. Árið 1975 var síðan stofnað embætti sóknarprests og Fella- og Hólahverfið gert að sérstöku prestakalli. Ráðinn var prestur að hinum unga söfnuði, séra Hreinn Hjartarson. Starfsaðstaða hins nýja safnaðar var að vonum frumstæð en með sameinuðum krafti og dugnaði var hafist handa að byggja upp starfsaðstöðu og skipuleggja safnaðarstarfið. Fyrst var messað í Fellaskóla við fremur erfiðar aðstæður en hlýhugur skólastjórnenda og velvilji þeirra auðvelduðu það starf. Vorið 1975 festi söfnuðurinn kaup á einbýlishúsi að Keilufelli 1 og það gert að safnaðarheimili og messuhald flutt þangað. Það hús var síðar selt og helgihaldinu fundinn staður í Gerðubergi.

Ljóst var á þessum tíma að sóknirnar hér í Efra-Breiðholti yrðu tvær, Fellasókn og önnur sókn í Hólahverfinu. Samkvæmt venju stóð til að byggja tvær kirkjur, eina í Fellahverfi en aðra fyrir Hólahverfið. Framsýnir menn með sr. Hrein og Árna Gunnarsson í fararbroddi komu því til leiðar að sameina sóknirnar í einni kirkju. Þetta mun vera einsdæmi hér á landi að tvær stórar sóknir sameinist um eina kirkju. Íbúafjöldi sóknarinnar, sem fékk nafnið Fella- og Hólasókn var á þessum tíma um 10.000 manns. Þessi ákvörðun um að byggja eina kirkju í stað tveggja hefur reynst mikið gæfuspor því samstarf og samvinna sóknanna hefur gengið afar vel og hagur beggja af þessari tilhögun.

Vorið 1987 var síðan formlega stofnað nýtt prestakall og söfnuður, Hólabrekkusókn. Þá um haustið var kosinn fyrsti sóknarprestur hinnar nýju sóknar og hlaut sr. Guðmundur Karl Ágústsson kosningu og starfar hann enn sem sóknarprestur Hólabrekkuprestakalls

Fella- og Hólakirkja

Þegar ákveðið var að byggja eina kirkju fyrir bæði hverfin var hafist handa um undirbúning byggingarinnar. Skyldi kirkjan heita Fella- og Hólakirkja. Að lokinni samkeppni um teikningu kirkjunnar var samþykkt að kaupa tillögu arkitektanna Ingimundar Sveinssonar og Gylfa Guðjónssonar.

Fyrsta skóflustungan af Fella- og Hólakirkju var tekin á pálmasunnudag 1982. Formaður bygginganefndar var kosinn Jón Hannesson, byggingameistari. Haraldur Sumarliðason var ráðinn sem byggingameistari kirkjunnar.
Hún var byggð í áföngum og fyrst messað í safnaðarheimilinu. Kirkjan var vígð formlega á pálmasunnudag 1988.

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 benda til himins

Fullyrða má að mjög vel var staðið að byggingu kirkjuhússins, vandað til verka og hugsað vel um að húsið yrði í senn heppilegt undir þá starfsemi sem þar fer fram og bæri reisn og fegurð sem tilhlýðilegt er en án óþarfa íburðar. Það er líka ljóst að allir sem að verkinu komu vönduðu verk sitt og miklar kröfur voru gerðar um efnisval. Kirkjan 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 og fundarherbergi. Milli hæða er lyfta auk stiga.

Komið er inn í rúmgott anddyri sem er lagt gráum steinflísum. Þaðan er gengið  inn í sjálft kirkjuskipið, en sams konar flísar þekja þar gólf og veggi upp að gluggabandi. Á göngusvæðum, kórtröppum og víðar er gólf lagt ljósum marmaraflísum. Loftið er viðarklætt.

Þegar gengið er inn vekja gluggarnir í kirkjuskipinu athygli. Þetta eru steindir gluggar í gluggaböndum með táknum og orðum úr Heilagri ritningu.

Altaristaflan er  úr steindu gleri og þemað í henni er  krossfestingin og upprisan. Hún hangir skáhallt yfir altari. Einnig er hangandi glerlistaverk í miðri kirkju. Verkið sýnir sjö dúfur sem tákna gjafir andans. Öll þessi listaverk eru eftir Leif Breiðfjörð glerlistamann. Fyrstu verkin voru sett upp árið 1997 og restin ári síðar. Samtímis vann Sigríður Jóhannesdóttir textílhönnuður, eiginkona Leifs,  allan messuskrúða kirkjunnar, en hún tók mið af byggingarstíl kirkjunnar og litum í glerlistaverkunum við þá vinnu.

Tvö þrep eru upp á kórpall,en þar er altari úr blágrýti og marmara. Predikunarstóll er vinstra megin við altari þegar horft er inn kirkjuskipið. Hann er  úr blágrýti. Hægra megin við altarið er skírnarfontur gerður úr  marmara. Til hliðar við predíkunarstólinn er gengið inn í skrúðhús.  Þangað er hægt að ganga utanfrá. Inn af skrúðhúsi er snyrting.

Kirkjan tekur  u.þ.b  350 manns í sæti. Hún er búin samtengdum eikarstólum með ljósgráu áklæði. Yfir inngang í kirkjuskipið er söngloft. Þar er orgel og söngpallar fyrir kirkjukórinn, rúmgóð skrifstofa organista og geymslur.

23ja radda pípuorgel frá Marcussen og Søn Orgelbyggeri í Danmörku er í kirkjunni og var vígt þann 31. maí árið 1992. Það hefur tvö nótnaborð og fótspil. Orgelhúsið er úr furu og fellur vel að byggingarstíl kirkjunnar. Orgelið þykir afar hljómgott enda er Fella- og Hólakirkja rómuð fyrir framúrskarandi hljómburð og vinsæl til tónleikahalds og fyrir upptökur á tónlist.

Þ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.

Í safnaðarsal og kennslustofu er hægt að leggja á borð fyrir 150 manns. Þar er píanó.  Í safnaðarsal hanga myndlistarverk eftir Steinunni Einarsdóttur. Þau skírskota til sálmsins „Eigi stjörnum ofar“.

Að safnaðarsalnum liggur rúmgóð kennslustofa aðskilin með færanleggum vegg og má opna á milli til að stækka rýmið. Meðfram kennslustofunni er manngengur geymslugangur. Frekar lítið en vel búið eldhús liggur að safnaðarsalnum.

Hægra megin frá aðalanddyri er gengið inn á  gang þar sem er ræstiherbergi, fatahengi og snyrtingar karla og kvenna. Her er gott aðgengi fyrir fatlaða.  Á ganginum er aðstaða til að setjast, sófar, borð og myndir eftir Þorgerði Sigurðardóttur á veggjum. Þar er líka fallegt líkan af kirkjunni, gert af Hrafnhildi Magnúsdóttur.

Glerskáli var byggður 1991 út frá gangarýminu. Þaðan liggur stigi niður á neðri hæð. Við stigann er lítil skrifstofa sem nýtist starfsmönnum barna- og æskulýðsstarfsins.

Á neðri hæð er fundarherbergi og skrifstofa gjaldkera. Þar er einnig rými sem er nýtt undir spil og leiki í barna- og æskulýðsstarfi. Inn af pallinum er sérstakur gangur þar sem eru skrifstofur presta og djákna og kirkjuvarða. Þar er einnig geymsluherbergi með ljósritunaraðstöðu o.fl.

Kirkjan á þrjár kirkjuklukkur sem eru í sérstökum klukknaturni við kirkjuna. Þær voru keyptar 1991. Á kirkjuklukkur.is má heyra hljóm þeirra og skoða myndir.

Á vegg við aðalinngang kirkjunnar er stór kross.

Við inngang kirkjunnar er fánastöng og hjólastandur