В навигацию 1576 г. с одним из голландских кораблей Генриху Штадену удалось, наконец, покинуть Россию.
Обогнув Нордкап, корабль взял курс по норвежским фьордам на Берген и дальше на Голландию. Первая часть пути прошла благополучно. Но по Северному морю пришлось итти с большою осторожностью. Не говоря об обычных для того времени пиратах, голландцам надо было особенно остерегаться встречи с испанскими судами, а кораблю, с которым Штаден и какие-то русские купцы везли свои товары, эти встречи были бы вдвойне опасны. Корабль имел на борту до 500 центнеров (около 200–300 пудов) каменных ядер для стенобитных орудий, закупленных голландскими повстанцами на скандинавском севере. Дело было в самый разгар нидерландской революции, когда ставший во главе северных революционных провинций Вильгельм принц Оранский настойчиво продолжал борьбу за независимость их от испанского владычества и подготовлял почву для соглашения с южными (фламандскими и валлонскими) провинциями, остававшимися верными испанской короне.
Едва избегнув опасной встречи с испанскими галерами, корабль достиг Голландии. Генрих Штаден с одним из русских торговых людей отправился в Лейпциг, где расторговался мехами с немецкими купцами и между прочим с некиим Генрихом Крамером, может быть, тем самым, который за два года до того, в 1574 г., побывал в Москве, самозванно прикрывшись званием дипломатического посланника.
На возвратном пути из Германии в Голландию, где-то около Гертогенбоша, на границе Северного Брабанта, Генрих Штаден был арестован и едва не подвергся пытке и казни, может быть, по подозрению в шпионстве.
Позже он появляется в Швеции, где безуспешно хлопочет о проезжей грамоте от короля для проезда в Москву. По этому же делу он ездил в Эмбден, но также безрезультатно. Оттуда по поручению Карла герцога Зюдерманландского Генрих Штаден был в Голландии: он должен был навести справки о русских торговых людях, времени их отплытия и маршруте. Герцог Карл готовил в это время (дело было ранней весной 1577 года) обычное пиратское нападение на торговый караван русских купцов.
Штаден выполнил данное ему поручение герцога и вернулся к нему в Ост-Фрисландию, но герцога там не застал; он уехал в Вогезы в Люцельштейн к своему шурину пфальцграфу Георгу Гансу. Туда же направился и Штаден и там вручил герцогу Карлу свое донесение.
Представленный пфальцграфу, Генрих Штаден, московский опричник, необычайно заинтересовал его своими рассказами о московитах, о «великом князе» и политическом положении Московии. Пфальцграф, только что прибывший с Регенсбургского рейхстага, пылал мечтой об имперском флоте, об узаконенном морском пиратстве и о борьбе с «нехристями-московитами».