A házaspár európai útja során több országot is bejárt. Németországban ellátogattak a dachaui koncentrációs táborba, ahol Paulo jelenést látott, melyben egy férfi szerepelt. Két hónappal később egy amszterdami kávézóban találkozott ezzel a férfival, akivel hosszan beszélgettek, eszmét cserélve tapasztalataikról és nézeteikről. A férfi, akinek kilétét Paulo máig titokban tartja, azt javasolta, hogy térjen meg a katolikus hithez. Ezután Paulo tanulmányozni kezdte a kereszténység szimbólumvilágát. A férfi arra is rávette, hogy járja végig a Santiago de Compostelába vezető, a középkor óta rendkívül fontos zarándokutat Franciaország és Spanyolország között.

1987-ben, egy évvel a zarándokutat követően Paulo megírta első könyvét, A zarándoklat (Egy mágus naplója) címmel. A könyvben a zarándokút alatti élményeit írja le, és azt a felfedezését, miszerint a hétköznapi ember életében is történnek csodák. Ezt a művét egy kis brazil kiadó jelentette meg, de — bár a sajtó alig foglalkozott vele — így is sikerkönyv lett.