Historia ya parokia ya Utatu Mtakatifu ina asili yake iliyojengwa katika misingi ya Umoja, Upendo na Ushirikiano ulioanzia mwaka 1995. Wazo la ujenzi wake liliwahusisha mlezi wa chaplaincy ya Chuo Kikuu Padre Severine Msemwa, wakatoliki waishio Changanyikeni na Parokia ya Mtakatifu Paulo Msewe. Kwa pamoja walikubaliana huduma za kiroho kutolewa sehemu ya Changanyikeni, hasa kutokana na changamoto kubwa ya kuvuka mto wakati wa masika kwenda Msewe na pia ukweli kwamba huduma za kiroho za chaplaincy ya Chuo Kikuu ilikuwa mahususi kwa ajili ya wanafunzi wa Chuo Kikuu hali ambayo haikukidhi mahitaji ya walei kikamilifu. Waamini wa Changanyikeni waliunda uongozi mdogo wa kuongoza kikundi chao cha sala, mwenyekiti akiwa Richard Silo, Katibu Laura mapunda, na Katibu msaidizi akiwa Fortunatus Mkawe.
Parokia ya Mt. Paulo Msewe na Chaplaincy ya Chuo Kikuu waliendelea kwa pamoja kuwahudumia waumini wa changanyikeni, kusimamia na kupitisha mpango wa kujenga kigango cha Changanyikeni kati ya mwaka 1996 mpaka 2002. Mfano masuala yote ya kiutawala ya wanachanganyikeni yalishughulikiwa na parokia ya Mt. Paulo Msewe na masuala ya kiroho yalishughulikiwa na Parokia ya Chuo Kikuu. Aidha wakati wote mwakilishi wa waumini wa Changanyikeni ndugu Richard Sillo alikuwa akishiriki mikutano yote katika parokia zote mbili. Kila jambo lilifanyika katika hali ya ushirikiano (Waumini wa Changanyikeni + Chuo Kikuu + Ubungo Msewe).
Changamoto huwa hazikosekani penye mafanikio, mfano kuna wakati pia kulitokea tofauti kidogo kati ya waumini wa changanyikeni na maparoko wote wawili hasa pale kamati ya ujenzi Changanyikeni ikishirikiana na paroko msaidizi wa Msewe padre Fernando walipofanya uamuzi wa haraka wa kununua eneo ambalo lilionekana zuri, bila kumshirikisha aliyekuwa Paroko wa Mt. Paulo Msewe wakati huo Padre Lucio, ambaye alikuwa safarini. Aliporudi alikuwa mkali, ikabidi waumini hao waende kuomba msamaha kwa maparoko wote, nao wakawasamehe, na kukubali kwa pamoja kwenda kulibariki eneo hilo.
Aidha mwaka 2003 maparoko wa chuo kikuu na Mt. Paulo Msewe walikubaliana rasmi kukiweka Kigango cha Changanyikeni chini ya usimamizi wa parokia ya Chuo Kikuu, kutokana na jiografia ili waumini hao waendelea kupata huduma za kiroho na kiutawala chini ya uongozi wa Monsinyori Deogratias H. Mbiku. Parokia ya Chuo Kikuu iliendelea kuratibu shughuli zote za maandalizi ya ujenzi wa Kigango cha Changanyikeni. Umoja katika kufanikisha shughuli ya utafutaji wa eneo uliendelea pale ambapo baadhi ya waasisi walijitolea kuipatia kigango sehemu ya maeneo yao, watu binafsi wenye maeneo karibu na eneo la kanisa waliiuzia kanisa kwa kiasi kidogo cha fedha na walio nje ya mipaka ya Changanyikeni walitupatia fedha na vitu mbalimbali vya kuanzia huduma katika kigango cha Changanyikeni.
Kutokana na umoja, upendo na mshikamano mkubwa kuwepo katika harakati za uanzishwaji wa kigango cha Changanyikeni. Muda wa Mungu ulipotimia haikuwa kazi ngumu kuipa Jina Jipya, Monsinyori Deogratias Mbiku kama msimamizi wa Changanyikeni akiongozwa na Nguvu ya Roho wa Mungu alitoa ufafanuzi kuwa hiki Kigango cha Mtakatifu Petro, ikifikia hadhi ya Parokia haitaitwa Parokia ya Mt. Petro kwa kuwa tayari kuna Parokia ya Mt. Petro Oysterbay. Kwa utaratibu haiwezekani, Jimbo mmoja kuwa na parokia mbili kutumia jina la Mt. Mmoja badala yake hii ya Changayikeni kutokana na Muundo wake wa kipekee itaitwa “Parokia ya Utatu Mtakatifu” jina hilo ilifurahiwa sana na wanakigango wote na kuendelea kusali ili Mwadhama Polycarp Kardinali Pengo aikubali na kwa Neema ya Mungu ndivyo ilivyokuwa mwezi Januari 2017 aliitamka kama parokia teule na siku ya Ijumaa, tarehe 7 mwezi wa 7, 2017,aliitangaza rasmi Parokia ya Utatu Mtakatifu Changanyikeni na kuitaja kama parokia ya 102 katika Jimbo kuu la Dar es Salaam wakati wa adhimisho ya Misa ya Upadrisho Msimbazi Senta.
