В 1563 г. он перебывал в ливонских замках и затем вторично попал в Ригу.
Здесь в декабре этого года Штаден был свидетелем жестокой казни Иоганна Арца, именовавшего себя графом, шведского наместника в Гельмете. Обвиненный герцогом Иоанном в изменнических сношениях с русскими, граф был растерзан раскаленными клещами.
Из Риги с одной только лошадью Штаден отправился в польский Вольмар, откуда польские отряды совершали свои набеги на пограничные русские области и в частности Юрьевский уезд, недавно отошедший к Москве (1558 г.). К этим вольмарским отрядам присоединился и Генрих Штаден; с ними он принимал участие в пограничных набегах и грабежах. Однажды, повздорив из-за дележа добычи, он попал в тюрьму.
Выйдя на свободу и «вдоволь насмотревшись на ливонские порядки», он махнул на Ливонию рукой и решил перебраться за рубеж, в таинственную и заманчивую Московию.
Понятно это решение бездомного вестфальца, дворового ливонских мыз и польского ландскнехта. То было время всеевропейской тяги на восток; то было время блестящих успехов Грозного. Счастье, казалось, бежало по пятам за «московитом». Не так давно прогремела его слава покорителя Казани и Астрахани. В прошлом году ему сдался литовский Полоцк (1563 г.) — ключ от Двины и Риги.
Счастливо миновав польские заставы на реке Эмбах и избежав неминуемой в случае поимки виселицы, Генрих Штаден пробрался к Дерпту. Там после отъехавшего 30 апреля 1564 г. к Сигизмунду II Августу кн. Андрея Михаиловича Курбского воеводой сидел боярин Михаил Яковлевич Морозов (1564 г.).
Через шесть дней Штаден был уже в Москве, в посольском приказе перед дьяком Андреем Васильевичем «у распросу». Он был взят толмачем в приказ; тогда же был пожалован поместным окладом в 150 четвертей и испомещен в Старицком уезде в селе Тесмино с деревнями, принадлежавшими до того одному из людей кн. Владимира Андреевича Старицкого (?).
Царь Иван был занят в то время мыслью о возрождении под русским протекторатом распавшегося в 1561 г. ливонского ордена. Предполагалось посадить магистром Вильгельма Фюрстенберга, взятого в плен в 1560 г. и проживавшего в Любиме, а преемником ему назначить сына последнего ливонского магистра Готгарда Кеттлера, — Вильгельма. Для переговоров Фюрстенберг был вызван в Москву (1564 г.). Но, как ленник Империи, он отклонил от себя предложение царя Ивана и был отправлен обратно в Любим, где и умер в январе следующего 1565 года.
В этих переговорах Генрих Штаден впервые выступил в своей новой роли толмача.
Получив от царя двор на Москве в «земщине» и, как иноземец, пользуясь правом курить вино, варить пиво и ставить мед, Генрих Штаден занялся обычным для иноземца занятием — корчемством. Не довольствуясь корчемными доходами, он завязывает связи с местными купцами-промышленниками и сборщиками мягкой рухляди с инородческих окраин Московского государства и занимается меховой торговлей.