Ο Επίσκοπος Λέοντβιν έγραψε ότι ο Στέφανος συνέλεξε λείψανα αρκετών αγίων στα «Κεσάρια» κατά τη διάρκεια της εκστρατείας του στα Βαλκάνια, μεταξύ των οποίων ο Άγιος Γεώργιος και ο Άγιος Νικόλαος.Τα δώρισε στη νέα τρίκλιτη βασιλική του αφιερωμένη στην Παναγία στο Székesfehérvár, όπου ίδρυσε επίσης ένα κεφάλαιο καθεδρικού ναού και τη νέα του πρωτεύουσα.Η απόφασή του επηρεάστηκε από το άνοιγμα, το 1018 ή το 1019, μιας νέας προσκυνηματικής διαδρομής που παρέκαμψε την παλιά του πρωτεύουσα, το Έστεργκομ.Η νέα διαδρομή συνέδεε τη Δυτική Ευρώπη και τους Αγίους Τόπους μέσω της Ουγγαρίας.Ο Στέφανος συναντούσε συχνά τους προσκυνητές, συμβάλλοντας στη διάδοση της φήμης του σε όλη την Ευρώπη.Ο ηγούμενος Odilo του Cluny, για παράδειγμα, έγραψε σε μια επιστολή προς τον Στέφανο ότι «όσοι επέστρεψαν από το ιερό του Κυρίου μας» μαρτυρούν το πάθος του βασιλιά «προς την τιμή της θεϊκής μας θρησκείας».Ο Στέφανος ίδρυσε επίσης τέσσερις ξενώνες για προσκυνητές στην Κωνσταντινούπολη, την Ιερουσαλήμ, τη Ραβέννα και τη Ρώμη.Εκτός από τους προσκυνητές, οι έμποροι χρησιμοποιούσαν συχνά την ασφαλή διαδρομή μέσω της Ουγγαρίας όταν ταξίδευαν μεταξύ Κωνσταντινούπολης και Δυτικής Ευρώπης.Οι θρύλοι του Στέφανου αναφέρονται σε 60 πλούσιους Πετσενέγους που ταξίδεψαν στην Ουγγαρία, αλλά δέχθηκαν επίθεση από Ούγγρους συνοριοφύλακες.Ο βασιλιάς καταδίκασε τους στρατιώτες του σε θάνατο για να αποδείξει την αποφασιστικότητά του να διατηρήσει την εσωτερική ειρήνη.