Odpowiadając na zaproszenie Bolesława do wykonania chrystianizacji Pomorzan, w podróż z Bambergu wyruszył 24 kwietnia 1124. Wybrał najzdolniejszych ze swego duchowieństwa, aby mu towarzyszyli i przygotował wszystko do podróży. Starał się nie powtórzyć błędu misjonarza Bernarda, który w 1123 pieszo przybył na misję w ubogich szatach i boso i z tego powodu został wyśmiany, a wkrótce i pobity. Przeciwnie niż swój poprzednik, Otto starał się jak najpiękniej zaprezentować na Pomorzu. Kupił błyszczące szaty kapłańskie, ozdoby ołtarzowe, kielichy i inne sprzęty kościelne, a także dużą liczbę wspaniałych szat, pięknych chust i innych kosztowności, które nadawały się na prezenty dla szlachetnych mieszkańców Pomorza. Chciał poprzez hojność przekonać pogańskich ludzi, że nie głosi chrześcijańskiej nauki z chciwości.
Do Gniezna dotarł przez Pragę, Niemczę, Wrocław i Kalisz. Książę Bolesław zapewnił mu towarzyszy, fundusze i zapasy na dalszą podróż. Powierzył opiekę nad biskupem doświadczonemu dowódcy wojennemu komesowi Santoka – księciu Pawłowi (Pawlikowi), który miał pod sobą 60 kawalerzystów.