В 1576 г. в Коле он сел на голландский корабль, который вез 500 центнеров каменных ядер для артиллерии инсургентов, боровшихся в Нидерландах против Испании; сам он увозил с собой большой груз мехов, которыми вместе с одним из русских купцов удачно расторговался на Лейпцигской ярмарке. Он и не думал покидать совсем и навсегда русскую землю.
Неистощимый на фантазии, он придумывает все новые и новые способы, чтобы вернуться в Московию, хотя бы и другим манером, чем раньше. Первый план состояв в том, чтобы поступить на службу к врагу Москвы – Швеции: "Я предпринял свою поездку к королю шведскому и просил его о пропуске, чтобы на описанном Поморье получить мне долг с великого князя". Но, рядом с таким расчетом на мирные сделки с московским правительством, он принимает поручение от брата короля, герцога Карла Зюдерманландского, разузнать, есть ли в Голландии русские торговые люди, караван которых герцог мог бы перехватить на своих пиратских судах по дороге к Балтике. Разыскивая по Германии шведского принца, Штаден попадает к его родственнику пфальцграфу Георгу Гансу, безземельному князю империи, своего рода бездомному авантюристу, мечтающему о создании подобного шведскому германского флота для борьбы с "нехристями-московитами". Штаден крайне заинтересовал пфальцграфа своими рассказами о Московии. Оба искателя приключений, отлично спелись между собой: сначала через пфальцграфа, потом лично Штаден представил императору Рудольфу II ни более, ни менее как план завоевания Московской державы с севера: объехав вокруг Норвегии и высадившись в Коле и Онеге, предполагалось направить десант через Поморье, которое в предшествующие годы (1573-1576 гг.) Штаден успел так основательно изучить (об этом проекте будет речь ниже).
Этот план есть новое доказательство удивительной изобретательности и основательнейших географических и стратегических исследований и познаний Штадена: в нем предусмотрена и новая дипломатическая комбинация – союз Германской империи, выставляющей большое наемное войско, с королями шведским и польским; имеется в виду подчинение Московии императору; Ивана IV предполагается взять в плен и отвезти в Германию, где и держать под строгим надзором. Штаден – бродяга, спекулянт и прожигатель жизни не претендует на важную роль в грандиозном предприятии. Свою автобиографию он кончает очень скромным пожеланием: "Сильно и неоднократно тянуло меня при этом (т. е. во время дипломатических поездок по организации коалиции) в Русскую землю, в Москву, ко двору великого князя. Благодарение вседержителю богу, удостоившему меня пережить столь (великое)!"
