На Анадыре, к немалому удивлению, Стадухин встретился со своим давним соплавателем — казаком из Великого Устюга Семеном Дежневым. По словам известного советского арктического исследователя и историка Арктики Владимира Визе, «из‑за возникшей конкуренции в ограблении местного населения между казачьими отрядами установились враждебные отношения, порой доходившие до вооруженных столкновений». И в 1651 году казакам Стадухина пришлось покинуть Анадырский край, чтобы поискать «новых неведомых землиц», и уйти на реку Пенжину, а затем на Гижигу, откуда морем перебраться на реку Товуй. В дальнейшем его отряд перешел в Охотский острожек, но на этом любые сведения о нем исчезают. Так считали почти 350 лет.
Неожиданно для историков в одном из архивов Ленинграда в начале 1990–х годов нашлась чудом сохранившаяся челобитная царю Алексею Михайловичу от некоего служилого человека Ивана Казанца, написанная где‑то в середине XVII века. После длительной работы с документом выяснилось, что здесь рассказано еще о 15 годах путешествий Михаила Стадухина и его казаков.
С Анадыря вышли в неизвестность 50 смельчаков во главе со Стадухиным. «А как мы пошли с Анадырь морем, — доносил челобитчик, — видели нужи и бедности от моря потопу много». Он не указал, к какому берегу Камчатки пристал отряд, лишь записал, что здесь пришлось бросить кочи и отправиться по зимнему пути на нартах через Каменный Нос к реке Пенжине.
Стояли жестокие морозы и свирепствовали буйные ветры. Нарты с трудом ползли по глубокому снегу. А вокруг, по всему горизонту, были лишь скалы. От непогоды можно было укрыться только в снегу. Негде было пополнить запасы продовольствия. «И без хлеба на том волоку едва не померли», — сообщал Иван Казанец. Наконец, перейдя через Камчатский Нос и переправившись через реку Камчатку, отряд достиг Пенжины. Больше всего путешественников удивило, что ее берега оказались почти безлесными. «Лес добывали с великой нужею и с боем и за кровию».
На реке Пенжине построили 2 новых коча, поставили паруса и отправились дальше на юг, к желанной реке Гижиге, о которой коряки поведали, что «там соболей много и лесу много». Едва кочи вышли из устья реки, как поднялась буря: «И тут уносило меня в море трое суток». Уцелел только коч Стадухина, а другой был разбит. И все же путешественники достигли берегов Гижиги и в сентябре 1651 года поставили здесь «острожек». Всю зиму они собирали здесь сведения о реках, лежащих к югу.
В долине Гижиги жили коряки и юкагиры. Людей здесь было такое множество, что Стадухин не стал даже пробовать силой привести их в подданство России. Расстались казаки с «мужиками- юкагирами» мирно: построили суда из найденного на берегах леса и отправились в плавание по Охотскому морю. «Морской разбой» (шторм) многие дни их трепал. Несколько раз приходилось приставать к берегу чтобы залатать пробитые борта и дырявые паруса. Потом снова шли вперед. На плавание ушло целое лето, только 10 сентября 1652 года они достигли «Дирядны реки с сю сторону называемую Товуем».
Здесь отряд Стадухина поставил очередной «острожек» и прожил еще 5 лет, приводя жителей побережья Охотского моря под «высокую руку» России. За эти годы умерли от голода и ран 37 казаков. Летом 1658 года остатки отряда вернулись в Якутск, где за заслуги Михаил Стадухин получил чин казацкого десятника, а вскоре был поверстан в атаманы.
В 1666 году якутские власти направили его с небольшим отрядом в новый поход. Куда? Сегодня уже никто не скажет. По пути отряд подвергся нападению там, где не должно было быть врагов, и весь был перебит. Так трагически оборвалась жизнь одного из замечательных первопроходцев северо–востока Азии. В добрую память об исканиях казака Михаила Стадухина и его сотоварищей до нас дошли его так называемые «Распросные речи», где было сказано, что Новая Земля — это «остров–Камень, в мори пояс … промышленные люди смечают… ходят из Поморья, с Мезени на Новую Землю, и против Енисейского и Тазовского и Ленского устья тот Камень тож все одна, что называют Новою Землею». Знать, не зря искал неведомые землицы Михаил Стадухин.
«… А я, холоп твой Сенька, от них остался на Ковыме реке в острожке с служилым человеком со Вторым Гавриловым с товарищи, всего тринатцатью человеки для твоего государева ясашного збору. И те, иноземцы юкагири, видя нас, холопей твоих, немногих людей, собрався сот пять и больши, приходили к нам, холопям твои, к острожку приступом и обсадили нас в острожке, и многих переранили, меня холопа твоего Сеньку, в голову стрелою жезнецею ранили, и в острожке многие иноземцы к нам сильно вломились». И таковыми было большинство походов бесстрашного казака Семена Дежнева. Среди простых русских людей, вписавших немало блестящих страниц в историю российской географии, он занимал одно из виднейших мест.