Перейдя еще за один за Камень — Уральские горы — русские уже в 1601 году основали в Северо–Западной Сибири промышленный и административный центр — Старую Мангазею. В 1619 году в Западной Сибири был основан второй такой же центр — Енисейский острог (Енисейск). Опираясь на Мангазею и Енисейск, казаки стали предпринимать походы, на реку Лена. Слухи о богатствах «великой реки Лены» разносились по всей Сибири. Ее сравнивали с Мангазеей, некогда сказочно богатой мехами.

Путь из Мангазеи на Лену лежал по Нижней Тунгуске и по притоку Тите; далее волоком переходили на реку Чурку, впадающую в реку Чона — приток Вилюя, по которому и выходили на Лену. Путь из Енисейска шел сначала вверх по Верхней Тунгуске до устья Илима, по которому следовали до впадения в него реки Идермы. Здесь находился так называемый «Ленский волок», ведший казаков к верховью реки Муки; следуя по этой реке, они попадали в реку Купа, а затем в реку Кута — приток Лены.

Мангазейские казаки, закончив сбор ясака, обычно возвращались обратно, енисейские же казаки нередко селились на Лене. На почве сбора ясака между мангазейскими и енисейскими казаками проходили кровопролитные столкновения: «Меж себя у тех служивых людей для тое своей бездельныя корысти бывают бои, друг друга побивают до смерти».

В 1630 году на Лену двинулось несколько отрядов, причем отряд мангазейского казака Мартемьяна Васильева вернулся с двумя тысячами соболей; большую часть собранного ясака он утаил в свою пользу. В том же году с Енисея на Лену перешел енисейский казачий десятник Михалка Стадухин. Точных данных о его жизни не сохранилось. Известно, что через три года в составе отряда Постника Иванова он уже собирал ясак у тунгусов на реке Вилюй. В 1641 году Стадухин был направлен с казаками в «новое место Емокон» (Оймекон), где ему «видимо учинилось» увидеть новую реку — Колыму. Его спутниками стали; Семен Дежнев, Михаил Коневал, Павел Леонтьев, Денис Ерило, Вторка Гаврилов, Андрей Иванов и 9 безымянных казаков.

Спустившись по течению реки Индигирка, он морем прошел до устья Колымы. Вот как об этом походе вспоминал товарищ Дежнева по службе Федор Чукичев: «По морю шли две недели. А с устья Индигирки реки к востоку бежали парусом до усгь Алазейки реки, а вверх парусом и собою до юкагирского князца Ноочичана полтретья дни... до лесу. И у того лесу зимовье поставили». Но казаки долго на реке Алазея не задержались.

На следующий год они снова вышли в море и через две недели были на Колыме, по которой дошли до большой реки Анюя и срубили здесь еще один городок—ясачное зимовье — Нижнеколымский острог. Оно стояло на Стадухинской протоке, приблизительно в 20 километрах от нынешнего Нижнеколымска, основанного в 1773 году. На Колыме Стадухин пробыл год, после чего вернулся в 1645 году в Якутск. Но через два года он снова пошел на Колыму «из Якутцкого острогу итить на государеву службу в государевых судах Леною рекою, а из Лены вышел в море, а морем на Ковыму реку». Стадухину не посчастливилось пройти морем дальше поселка Игнатьева. Зато посчастливилось в ином — во время похода на тундровую реку Чукочья, где обитал оторвавшийся от основного племени чукотский род, он встретил смышленую и много знающую чукотскую женщину Калибу. Она и рассказала, что к северу от колымского устья имеется большой морской остров. Правда, что это за остров — будущий Врангеля, будущие Новосибирские или Ляховские острова, — он так и не узнал. Но все же оставил об острове письменный след. И в соответствии с полученными указаниями от местных охотников и промысловиков он разведал, есть ли там морской зверь морж.

Выйдя с Колымы летом 1649 года, Стадухин поплыл на восток, но предположительно от мыса Шелагского был вынужден повернуть обратно за неимением съестных припасов. Ввиду неудачи, которую Стадухин потерпел в попытке пройти морем на «новую реку Анадырь», он решил пробраться туда сухим путем. «Пришлось возвращаться на Яну реку и зимовать на ясашном зимовье». Здесь казаки остались до 1650 года. Затем часть своих спутников Стадухин оставил на Яне, приказав следующим летом «на коче идти в море», а сам с более чем полусотней служивых людей отправился на нартах «за волок», на Колыму…

Путешествие на нартах с Колымы на Анадырь продолжалось почти два месяца. Во время перехода через Камень (вероятно — Анюйский горный хребет) их настигли бурные ветры. Многие участники похода получили увечья или пострадали от сильных холодов.

На Анадыре, к немалому удивлению, Стадухин встретился со своим давним соплавателем — казаком из Великого Устюга Семеном Дежневым. По словам известного советского арктического исследователя и историка Арктики Владимира Визе, «из‑за возникшей конкуренции в ограблении местного населения между казачьими отрядами установились враждебные отношения, порой доходившие до вооруженных столкновений». И в 1651 году казакам Стадухина пришлось покинуть Анадырский край, чтобы поискать «новых неведомых землиц», и уйти на реку Пенжину, а затем на Гижигу, откуда морем перебраться на реку Товуй. В дальнейшем его отряд перешел в Охотский острожек, но на этом любые сведения о нем исчезают. Так считали почти 350 лет.

Неожиданно для историков в одном из архивов Ленинграда в начале 1990–х годов нашлась чудом сохранившаяся челобитная царю Алексею Михайловичу от некоего служилого человека Ивана Казанца, написанная где‑то в середине XVII века. После длительной работы с документом выяснилось, что здесь рассказано еще о 15 годах путешествий Михаила Стадухина и его казаков.

С Анадыря вышли в неизвестность 50 смельчаков во главе со Стадухиным. «А как мы пошли с Анадырь морем, — доносил челобитчик, — видели нужи и бедности от моря потопу много». Он не указал, к какому берегу Камчатки пристал отряд, лишь записал, что здесь пришлось бросить кочи и отправиться по зимнему пути на нартах через Каменный Нос к реке Пенжине.

Стояли жестокие морозы и свирепствовали буйные ветры. Нарты с трудом ползли по глубокому снегу. А вокруг, по всему горизонту, были лишь скалы. От непогоды можно было укрыться только в снегу. Негде было пополнить запасы продовольствия. «И без хлеба на том волоку едва не померли», — сообщал Иван Казанец. Наконец, перейдя через Камчатский Нос и переправившись через реку Камчатку, отряд достиг Пенжины. Больше всего путешественников удивило, что ее берега оказались почти безлесными. «Лес добывали с великой нужею и с боем и за кровию».

На реке Пенжине построили 2 новых коча, поставили паруса и отправились дальше на юг, к желанной реке Гижиге, о которой коряки поведали, что «там соболей много и лесу много». Едва кочи вышли из устья реки, как поднялась буря: «И тут уносило меня в море трое суток». Уцелел только коч Стадухина, а другой был разбит. И все же путешественники достигли берегов Гижиги и в сентябре 1651 года поставили здесь «острожек». Всю зиму они собирали здесь сведения о реках, лежащих к югу.

В долине Гижиги жили коряки и юкагиры. Людей здесь было такое множество, что Стадухин не стал даже пробовать силой привести их в подданство России. Расстались казаки с «мужиками- юкагирами» мирно: построили суда из найденного на берегах леса и отправились в плавание по Охотскому морю. «Морской разбой» (шторм) многие дни их трепал. Несколько раз приходилось приставать к берегу чтобы залатать пробитые борта и дырявые паруса. Потом снова шли вперед. На плавание ушло целое лето, только 10 сентября 1652 года они достигли «Дирядны реки с сю сторону называемую Товуем».