Willigis postanowił wysłać po Wojciecha poselstwo złożone z brata księcia czeskiego Strachkwasa Chrystiana i brata samego Wojciecha – Radła. Synod nakazał biskupowi powrót do Pragi, a ten po powrocie rozpoczął przerwaną wcześniej ewangelizację. Wkrótce potem wystąpił przeciwko księciu Bolesławowi, którego stronnik nakrył swoją żonę na cudzołóstwie. Kobietę chciano zamordować, a Wojciech stanął w jej obronie. Nie przyniosło to skutku, bo kobieta została stracona, a biskup ponownie opuścił Pragę i wyjechał do Rzymu.
W 996 roku, przebywając w Wiecznym Mieście, poznał Ottona III, z którym się zaprzyjaźnił. Jednocześnie dowiedział się, że większość jego rodziny została wymordowana przez Wrszowców – krewnych kobiety, której usiłował bronić. Jedynymi ocalałymi byli bracia: Sobiesław i Radzim Gaudenty. Czekając na możliwość powrotu do Pragi, wędrował po Europie, odwiedzając m.in. Moguncję, Tours, opactwo Fleury i księstwo Węgier, gdzie miał bierzmować Stefana I (na pewno nie chrzcił Gejzy). Pod koniec 996 roku otrzymał informację, że nie może wrócić do Pragi, podjął więc decyzję by wyruszyć na misję. Otton III poradził mu by wybrał się do Prus. Prawdopodobnie konsultował się w tej sprawie także z Bolesławem Chrobrym. W kwietniu 997 roku dotarł do Gdańska, gdzie nauczał i udzielał chrztów.