Prócz dobrych stosunków z cesarzemNiemiec, Bolesław Chrobrystarał się mieć dobre kontakty także papieżem, i gdy Polskę odwiedził biskuppraski Wojciech (był znaną postacią, cieszącą się szacunkiem cesarstwa i papieża) z misją szerzenia chrześcijaństwa wśród Prusów, nadarzyła się dogodna ku temu okazja. Bolesław wsparł go wówczas i zorganizował wyprawę, która jednak zakończyła się męczeńską śmiercią Wojciecha w 997 r., przez co papież uczynił go świętym. Wydarzenie to przyniosło Bolesławowi myśl o utworzeniu w Polsce arcybiskupstwa, więc wykupił od Prusów ciało św. Wojciecha i złożył je w gnieźnieńskimkościele jako relikwie. Po czym papież Sylwester II utworzył w mieście arcybiskupstwo w 999 r., a w 1000 r. Otton III (cesarz niemiecki) udał się tam z pielgrzymką, by odwiedzić grób św. Wojciecha.