Biskup Leodvin je zapisao da je Stjepan tijekom svog pohoda na Balkan u "Cesarijima" sakupio relikvije brojnih svetaca, uključujući svetog Jurja i svetog Nikolu.Darovao ih je svojoj novoj trobrodnoj bazilici posvećenoj Presvetoj Djevici u Székesfehérváru, gdje je također uspostavio katedralni kaptol i svoju novu prijestolnicu.Na njegovu odluku utjecalo je otvaranje, 1018. ili 1019. godine, nove hodočasničke rute koja je zaobilazila njegovu staru prijestolnicu Esztergom.Nova ruta povezivala je zapadnu Europu i Svetu zemlju preko Mađarske.Stjepan se često susretao s hodočasnicima, što je pridonijelo širenju njegove slave diljem Europe.Opat Odilo od Clunyja, primjerice, napisao je u pismu Stjepanu da "oni koji su se vratili iz svetišta našega Gospodina" svjedoče o kraljevoj strasti "prema časti naše božanske religije".Stjepan je također osnovao četiri hostela za hodočasnike u Carigradu, Jeruzalemu, Ravenni i Rimu.Osim hodočasnika, sigurnim putem preko Ugarske često su se koristili i trgovci koji su putovali između Carigrada i zapadne Europe.Stjepanove legende govore o 60 bogatih Pečenega koji su putovali u Ugarsku, ali su ih napali mađarski graničari.Kralj je osudio svoje vojnike na smrt kako bi pokazao svoju odlučnost da očuva unutarnji mir.