Leodvin püspök azt írta, hogy István balkáni hadjárata során számos szent ereklyéit gyűjtötte a „Cesáriumban”, köztük Szent György és Szent Miklós ereklyéit.A Szent Szűz tiszteletére szentelt háromhajós bazilikájának adományozta őket Székesfehérváron, ahol székesegyházi káptalant és új fővárosát is felállította.Döntését befolyásolta, hogy 1018-ban vagy 1019-ben megnyílt egy új zarándokút, amely elkerülte régi fővárosát, Esztergomot.Az új útvonal Magyarországon keresztül kötötte össze Nyugat-Európát és a Szentföldet.István gyakran találkozott a zarándokokkal, hozzájárulva hírnevének Európa-szerte való terjedéséhez.Odilo cluny-i apát például azt írta Istvánnak írt levelében, hogy „azok, akik visszatértek Urunk szentélyéből”, a király „isteni vallásunk tisztelete iránti szenvedélyéről” tanúskodnak.István négy szállót is alapított a zarándokok számára Konstantinápolyban, Jeruzsálemben, Ravennában és Rómában.Konstantinápoly és Nyugat-Európa között a kereskedők a zarándokok mellett gyakran használták a biztonságos Magyarországot átszelő útvonalat.István legendái 60 gazdag besenyőre vonatkoznak, akik Magyarországra utaztak, de a magyar határőrök megtámadták őket.A király halálra ítélte katonáit, hogy demonstrálja eltökéltségét a belső béke megőrzése mellett.