Keď sa Norbert rozlúčil zo Xanténom, odložil svoj baranicový plášť a obliekol si vlnené šaty a plášť. Kráča pešo a naboso. Za Norbertom kráčajú jeho dvaja spoločníci s mulicou, na chrbte ktorej je ich spoločná batožina. Medzitým v správe Cirkvi nastala zmena. V roku 1118 zomrel pápež Pascal II. a zvolili nového, ktorý pod menom Gelasius II. započal svoj pontifikát 24. januára 1118. Nemeckému cisárovi sa však nepáči, a tak sa poponáhľal do Talianska, kde v noci vnikol do mesta a svojvoľne si zvolil nového pápeža. Ten bol dosť odvážny na to, aby si privlastnil odznaky pápežskej moci a prijal meno Gregor VIII. Gelasius sa rozhodol opustiť Rím a utiahol sa do Francúzska. Táto zvesť sa čoskoro rozniesla po celej Európe, a keď sa o tom dozvedel Norbert, rozhodol sa, že vyhľadá pápeža.Po dlhej a namáhavej púti i napriek zimnému počasiu sa Norbert dostal až do mestečka Saint Gilles, ktoré si Gelasius zvolil za svoje útočište. Norbert, ako každý pútnik, vošiel do baziliky a vyhľadal hrob svätého Gillesa, aby si pri ňom pokľakol a prosil za svoje hriechy. Potom prosil o audienciu u pápeža. Skloniac sa k nohám prenasledovaného kniežaťa Cirkvi rozpovedal mu o sebe všetko. Gelasius hneď spoznal, že má pred sebou Božieho muža a ponúka Norbertovi miesto vo svojich službách. Norbert sa odvoláva na svoj život na kráľovskom dvore a bráni sa tomuto novému úradu, ale je ochotný prijať každé rozhodnutie pápeža. Gelasius ho s láskou vypočul a pochopil. Dovoľuje mu, aby slobodne opustil veľkňazský dvor a dáva mu splnomocnenie, aby mohol stále hlásať Božie slovo. Na potvrdenie toho mu vystavuje dokument, v ktorom ho menuje za apoštolského vierozvestca. Norbert i napriek krutej zime sa ihneď vyberá na svoju novú misiu. V priebehu troch až štyroch mesiacov dvakrát prešiel celé Francúzsko.
Keď raz Norbert so svojimi spoločníkmi prišiel do Valencie, boli jeho spoločníci nadmerne vyčerpaní a ochoreli. Norbert sa o nich stará, ale napriek jeho snahe, chorobe podľahli. V čase, keď ešte Norbert opatroval svojich chorých spoločníkov, bolo to počas Veľkého týždňa, prišiel do Valencie cambraiský biskup Buchard. Keď sa to dozvedel Norbert, túžil ho navštíviť, lebo ho s ním spojilo dávne priateľstvo. Išiel teda do domu, kde biskup býval a pod bránou sa stretá s mladým kňazom i prosí ho o sprostredkovanie prijatia u biskupa. Tento mladý kňaz sprvu váha, ale potom Norberta ohlási u biskupa.
Norbert biskupa pozdravil po nemecky a po krátkom rozhovo
re biskup spoznáva svojho bývalého priateľa. Prešlo niekoľko minút, čo prebiehali prejavy priateľských citov. Kňaz, ktorý Norberta doviedol k biskupovi, je síce svedkom tejto dojímavej udalosti, ale keďže nerozumie po nemecky, nemôže vedieť, o čo ide. Slzy biskupa však prezrádzajú veľké pohnutie zo stretnutia týchto dvoch priateľov. Preto kňaz pristúpil k biskupovi a spýtal sa: Pane môj, čo to znamená a kto je ten cudzinec? Biskup odpovedal: Ten, koho tu vidíš, bol so mnou niekoľko rokov na kráľovskom dvore a jemu môžem ďakovať, že som biskupom, lebo prv než by mi bol panovník biskupstvo udelil, Norbert sa ho zriekol. Pohnuté slová biskupa a pohľad na vznešeného kajúcnika dojali mladého kňaza až k slzám. Veď i on cíti v duši túžbu po rehoľnom živote. Aj on chce opustiť svetskú slávu, aby sa mohol bezvýhradne zasvätiť službe Bohu.
re biskup spoznáva svojho bývalého priateľa. Prešlo niekoľko minút, čo prebiehali prejavy priateľských citov. Kňaz, ktorý Norberta doviedol k biskupovi, je síce svedkom tejto dojímavej udalosti, ale keďže nerozumie po nemecky, nemôže vedieť, o čo ide. Slzy biskupa však prezrádzajú veľké pohnutie zo stretnutia týchto dvoch priateľov. Preto kňaz pristúpil k biskupovi a spýtal sa: Pane môj, čo to znamená a kto je ten cudzinec? Biskup odpovedal: Ten, koho tu vidíš, bol so mnou niekoľko rokov na kráľovskom dvore a jemu môžem ďakovať, že som biskupom, lebo prv než by mi bol panovník biskupstvo udelil, Norbert sa ho zriekol. Pohnuté slová biskupa a pohľad na vznešeného kajúcnika dojali mladého kňaza až k slzám. Veď i on cíti v duši túžbu po rehoľnom živote. Aj on chce opustiť svetskú slávu, aby sa mohol bezvýhradne zasvätiť službe Bohu. Po veľkonočných sviatkoch a po smrti troch Norbertových spoločníkov, sám Norbert vážne ochorel. Musel sa preto uspokojiť, že vo Valencii pobudne dlhší čas. Mladý kňaz, ktorý bol svedkom stretnutia Norberta s biskupom, menom Hugo, horlivo navštevuje Norberta. Čím dlhšie ho pozná, tým viac ho obdivuje. Hugo sa rozhodol nasledovať Norberta, ale najprv sa chce vrátiť do svojho rodiska, aby tam usporiadal svoj majetok. Keď sa Hugo vrátil, obaja sa spoločne vydali na cestu. Žili chudobne ako Kristus a za svoje služby nežiadali nič. Malé dary, ktoré veriaci kládli na oltár pri svätej omši, si nenechali len pre seba. Rozdelili sa s potrebnými. Starosti o každodenné potreby ponechávali na Božiu prozreteľnosť. Nepovažovali za správne, aby po ľudskej odmene túžili tí, ktorí pre Krista všetkým opovrhli. Cítili sa na zemi cudzincami a pútnikmi, preto všetky svoje túžby smerovali k nebeskej vlasti. Takéto hrdinské sebazapieranie, prirodzene, strhávalo mysle a dojímalo srdcia. Keď sa Norbert spolu s Hugom blížili k nejakému mestu či dedine, ľudia ich očakávali s veľkým oduševnením. Nuž, kto by neobdivoval tento nový, skoro anjelský spôsob života.
Norbert je nám často predstavovaný ako zvestovateľ pokoja. Svojou veľkou horlivosťou, múdrosťou a jemnocitom zmieroval nepriateľov. Bol to veľký dar, ktorý dostal od Pána Boha, a ktorý si nenechal iba pre seba. Raz sa Norbert stretol s mladíkom, ktorému v tom týždni zavraždili brata. Mladík bol veľmi nahnevaný a túžil po pomste, chcel sa doslova vrhnúť na vrahov. Norbert ho však zastavil. Pozdravil sa mu a nežne ho objal: Priateľu, som tu cudzincom a cestujem týmto krajom. Odkedy som sem prišiel, od nikoho som nič nežiadal, ani neprijal. Vidím, že si láskavý a v kvete mladosti. Bolo by mi veľmi milé, keby si mi ponúkol dar, ktorý by som si odniesol z tohto miesta. Pán Boh ťa za to odmení. Mladík dojatý, so slzami v očiach odpovedal: Hovor, otec, nič ti neodopriem. Norbert povedal: Prosím o milosť pre tvojho brata. Aká to obdivuhodná moc, aká vznešená a podmaňujúca sila lásky! Zúrivý lev sa zmenil na nežného baránka. Mládenec sa zriekol pomsty a stal sa najhorlivejším pomocníkom pri uzmierovaní nepriateľov v celom kraji.
Dňa 29. jaunára 1119 však nečakane zomiera prvý ochranca Norberta, pápež Gelasius II. Novým pápežom bol zvolený arcibiskup Guy, strýc francúzskej kráľovnej, ktorý prijal meno Kalixt II. Ten zvolal snem do Remeša, a aj Norbert sa tam vybral, aby si vyžiadal nielen súhlas k horlivému plneniu započatého apoštolátu, ale aj požehnanie od novozvoleného pápeža. Už tri dni bol v Remeši a hľadal príležitosť dostať sa k pápežovi, ale márne. Rozhodol sa preto, že opustí mesto. Ako tak so svojimi spoločníkmi, Hugom a ešte jedným kňazom odpočívali, priblížil sa k nim akýsi sprievod. Je to laonský biskup Bartolomej, ktorý sa ponáhľa na snem. Veľkňaz sa mimovoľne zastavil a pozdravuje neznámych pútnikov. Ktože ste? Spýtal sa ich. Norbert mu v krátkosti vyrozprával svoj životný príbeh a dodal: Prišiel som do Remeša, aby som si vyžiadal požehnanie od Svätého Otca, právo hlásať evanjelium a poradiť sa s ním o ďalších mojich zámeroch, lebo vo všetkom sa chcem opierať o autoritu Apoštolskej stolice. Bartolomej dojatý spoznal, že sa stretáva s Božím vyslancom, a že pod chatrným odevom sa skrýva ozajstná perla. Vyzval teda Norberta, aby sa vrátil do Remeša, že ho predstaví pápežovi.
Dňa 16. alebo 19. októbra 1119 prišiel Bartolomej s Norbertom a jeho dvomi spoločníkmi do Remeša. Bartolomej bol Kalixtovým synovcom, takže ich pápež prijal. Šťastný Norbert vyrozprával pápežovi všetko o svojej misionárskej činnosti a o tom, ako túži po dokonalejšom rehoľnom živote. Preto ho poprosil, aby obnovil dokument, ktorým bol vymenovaný za apoštolského misionára jeho predchodcom. Kalixt sa potešil, že môže podporovať tohto nečakaného spolupracovníka. Pochválil Norberta a dal mu žiadané splnomocnenie. Rád by sa s Norbertom ešte viac porozprával, ale povinnosti mu v tom bránili. Poprosil teda Bartolomeja, aby u seba v Laone zdržal Norberta, že sa tam po sneme opäť všetci stretnú.Pobyt v Laone bol Norbertovi len na úžitok, lebo sa zdokonaľoval vo francúzskom jazyku a mohol sa tu stretať s niektorými členmi svojej rodiny. V novembri splnil pápež Kalixt II. svoj sľub a prišiel do Laonu. Norbert bol v biskupskom paláci denným hosťom. Mal mnoho príležitostí voľne sa stýkať s pápežom a počúvať jeho rady. Pápež mu radil, aby zanechal túlavý život a založil rehoľu, ktorá by sa okrem nazerania, venovala činnému životu. Aj Bartolomej požiadal Norberta, aby zostal v jeho diecéze. Naučil sa vážiť si poklad, ktorý mu zveril pápež.
