Paavi Johannes Paavali II piti 11.10.1985 tärkeän puheen Euroopan Piispojen Konferenssin Neuvostossa. Analysoituaan Euroopan maallistumista hän sanoi lyhyesti, että on tarvetta Euroopan uuteen evankeliointiin.
     ”Tehokkaan evankelioinnin toteuttamiseksi meidän täytyy palata alkuperäiseen apostoliseen malliin. Tätä perustavanlaatuista ja esimerkillistä mallia me voimme ihaillen katsella viimeisellä aterialla. Siinä apostolit ovat yhdessä Marian kanssa ja odottavat hellittämättömästi Pyhän Hengen lahjaa. Evankeliointi voi alkaa ainoastaan Pyhän Hengen vuodattamisesta. Hengen lahja on ensimmäinen liikkeelle paneva tekijä, ensimmäinen lähde, ensimmäinen aidon evankelioinnin puhallus. Evankeliointi tulee siis aloittaa kutsumalla Henkeä ja etsimällä, missä Hän puhaltaa (vrt. Joh. 3: 8). Joitakin oireita tästä Hengen puhaltamisesta ilmenee varmasti Euroopassa tänään. Niiden löytämiseksi, tukemiseksi ja kehittämiseksi on joskus tarpeen luopua kangistuneista kaavoista ja mennä sinne, missä on alkamassa 'Hengen mukainen' elämä.”
     Myöhemmin, 15.1.1986, Paavi lähetti Neokatekumenaalisen Tien aloittajien ehdotuksesta muutamia perheitä tekemään ns. ”implantatio ecclesiae” Euroopan maallistuneimpiin paikkoihin. Lähetystyön tarkoitus oli tuoda esiin kristillinen yhteisö, jossa olisi silmin nähtävissä uskon vaikutus nykypäivänä. Lähetettävien joukkoon kuului Pasinaton perhe. Se asettui isä Marino Trevisinin tukemana ja piispa Paul Verschurenin hyväksymisen myötä Ouluun, jossa Katoliseen Kirkkoon kuuluvia oli vain vähän.
     Lyhyen ajan kuluttua ja monien katolisten maahanmuuttajien saapumisen jälkeen saatiin kuitenkin todeta, että oli tarpeen rakentaa Ouluun oma kokoontumispaikka. Näin alettiin suunnitella Oulun katolista kirkkoa.
     Arkkitehti Gabriele Geronzi teki rakennussuunnitelman. Hän sai inspiraation mallista, jonka Kiko Argüello oli laatinut 14.9.1987, Pyhän Ristin ylentämisen päivänä. Suunnitelma esiteltiin Paaville, joka siunasi tulevan rakennuksen peruskiven vieraillessaan Suomessa vuonna 1989 ja lahjoitti Yasna Goran Pyhää Mariaa esittävän maalauksen. Nykyään maalaus on kirkossa presidentiaalisen istuimen yläpuolella. Lukuisten Italiassa ja Sveitsissä olevien neokatekumenaalisten yhteisöjen tuella rakennettiin kirkon ensimmäinen osa vuonna 1991, ja rakentaminen saatiin Saksan kirkon ”Bonifatiuswerkin” tukemana miltei päätökseen vuonna 2000.
     Kirkkosalin Mysteerienkruunun maalaukset ovat taidemaalari Kiko Argüellon ja hänen kolmen maalariavustajansa, Francisco Olivares Bogeskovin, David Lopezin ja Michele Benvenuton, tekemiä. Taideteos vaati puolentoista vuoden työn ja tehtiin ilmaiseksi rakkaudesta Kristusta ja Hänen kirkkoaan kohtaan.