Он работал в Любеке у своего кузена, затем перебрался в Ригу: в это время жители города были обеспокоены сведениями о том, что русский царь намерен захватить город. Штаден работал на городском валу, который спешно возводили, боясь прихода русских войск. Когда раздатчик денег заболел, Штаден с радостью взялся распределять марки среди работавших. Опять же по признанию самого Генриха, он «снабдил себя марками» так, «что... не пришлось уже больше работать на валу, и я мог спокойно прогуливаться по валу и осматривать его». Когда его двоюродный брат заметил ему, что он поступал плохо, Штаден испугался и бежал в Вольмар... Штаден скитался по Ливонии. Видя, что русскому царю удается его поход, и скоро вся Ливония станет его владением, Штаден решил перейти на службу Ивану Грозному и в 1564 г. оказался в Москве, в Посольском приказе, взятым на службу в качестве переводчика; тогда же он получил поместье в Старицком уезде. Получив от царя право на Москве, в «земщине», курить вино, варить пиво и ставить мед он стал заниматься также корчемством. В Москве у него появляются свои покровители. Когда Старицкий уезд был взят в опричнину, Генрих Штаден стал опричником, и даже участвовал в Новгородском походе. Ничего не стесняясь, он сам рассказывает, как грабил и убивал, увозя в Москву десятки возов с награбленным. После новгородского погрома Штаден был пожалован «вичем» — отныне его стали именовать Андреем Володимеровичем... В 1575-1576 гг. Штаден перебрался в Колу, чтобы оттуда отправиться за товаром в Европу. В 1576 г. он покинул Россию на норвежском корабле, на котором, кстати, везли в Голландию, где происходила революция, около 200-300 пудов каменных ядер для стенобитных орудий повстанцев Вильгельма Оранского. Чуть не встретившись в испанскими галерами, корабль благополучно достиг берегов Голландии. Штаден отправился в Германию. Позже он объявился в Швеции, где хлопотал, но безуспешно, о визе для проезда в Москву. О беспринципности Генриха Штадена свидетельствует то, что, по поручению Карла, герцога Зюдерманландского, бывший опричник ездил в Голландию навести справки о русских купцах — времени их отплытия. Герцогу нужно было знать это для обычного в то время пиратского нападения на караван. Штаден выполнил поручение и вернулся в Ост-Фрисландию, где уже не застал герцога, который отбыл в Вогезы в Люцельштейн к своему шурину пфальцграфу Георгу Гансу. Штаден отправился туда же со своим донесением. Пфальцграф заинтересовался рассказами Штадена о Московии Видимо, он попросил Штадена написать ему подробнее все, что тому было известно о «нехристях-московитах».