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