Перейдя еще за один за Камень — Уральские горы — русские уже в 1601 году основали в Северо–Западной Сибири промышленный и административный центр — Старую Мангазею. В 1619 году в Западной Сибири был основан второй такой же центр — Енисейский острог (Енисейск). Опираясь на Мангазею и Енисейск, казаки стали предпринимать походы, на реку Лена. Слухи о богатствах «великой реки Лены» разносились по всей Сибири. Ее сравнивали с Мангазеей, некогда сказочно богатой мехами.
Путь из Мангазеи на Лену лежал по Нижней Тунгуске и по притоку Тите; далее волоком переходили на реку Чурку, впадающую в реку Чона — приток Вилюя, по которому и выходили на Лену. Путь из Енисейска шел сначала вверх по Верхней Тунгуске до устья Илима, по которому следовали до впадения в него реки Идермы. Здесь находился так называемый «Ленский волок», ведший казаков к верховью реки Муки; следуя по этой реке, они попадали в реку Купа, а затем в реку Кута — приток Лены.
Мангазейские казаки, закончив сбор ясака, обычно возвращались обратно, енисейские же казаки нередко селились на Лене. На почве сбора ясака между мангазейскими и енисейскими казаками проходили кровопролитные столкновения: «Меж себя у тех служивых людей для тое своей бездельныя корысти бывают бои, друг друга побивают до смерти».
В 1630 году на Лену двинулось несколько отрядов, причем отряд мангазейского казака Мартемьяна Васильева вернулся с двумя тысячами соболей; большую часть собранного ясака он утаил в свою пользу. В том же году с Енисея на Лену перешел енисейский казачий десятник Михалка Стадухин. Точных данных о его жизни не сохранилось. Известно, что через три года в составе отряда Постника Иванова он уже собирал ясак у тунгусов на реке Вилюй. В 1641 году Стадухин был направлен с казаками в «новое место Емокон» (Оймекон), где ему «видимо учинилось» увидеть новую реку — Колыму. Его спутниками стали; Семен Дежнев, Михаил Коневал, Павел Леонтьев, Денис Ерило, Вторка Гаврилов, Андрей Иванов и 9 безымянных казаков.
Спустившись по течению реки Индигирка, он морем прошел до устья Колымы. Вот как об этом походе вспоминал товарищ Дежнева по службе Федор Чукичев: «По морю шли две недели. А с устья Индигирки реки к востоку бежали парусом до усгь Алазейки реки, а вверх парусом и собою до юкагирского князца Ноочичана полтретья дни... до лесу. И у того лесу зимовье поставили». Но казаки долго на реке Алазея не задержались.
На следующий год они снова вышли в море и через две недели были на Колыме, по которой дошли до большой реки Анюя и срубили здесь еще один городок—ясачное зимовье — Нижнеколымский острог. Оно стояло на Стадухинской протоке, приблизительно в 20 километрах от нынешнего Нижнеколымска, основанного в 1773 году. На Колыме Стадухин пробыл год, после чего вернулся в 1645 году в Якутск. Но через два года он снова пошел на Колыму «из Якутцкого острогу итить на государеву службу в государевых судах Леною рекою, а из Лены вышел в море, а морем на Ковыму реку». Стадухину не посчастливилось пройти морем дальше поселка Игнатьева. Зато посчастливилось в ином — во время похода на тундровую реку Чукочья, где обитал оторвавшийся от основного племени чукотский род, он встретил смышленую и много знающую чукотскую женщину Калибу. Она и рассказала, что к северу от колымского устья имеется большой морской остров. Правда, что это за остров — будущий Врангеля, будущие Новосибирские или Ляховские острова, — он так и не узнал. Но все же оставил об острове письменный след. И в соответствии с полученными указаниями от местных охотников и промысловиков он разведал, есть ли там морской зверь морж.
Выйдя с Колымы летом 1649 года, Стадухин поплыл на восток, но предположительно от мыса Шелагского был вынужден повернуть обратно за неимением съестных припасов. Ввиду неудачи, которую Стадухин потерпел в попытке пройти морем на «новую реку Анадырь», он решил пробраться туда сухим путем. «Пришлось возвращаться на Яну реку и зимовать на ясашном зимовье». Здесь казаки остались до 1650 года. Затем часть своих спутников Стадухин оставил на Яне, приказав следующим летом «на коче идти в море», а сам с более чем полусотней служивых людей отправился на нартах «за волок», на Колыму…
Путешествие на нартах с Колымы на Анадырь продолжалось почти два месяца. Во время перехода через Камень (вероятно — Анюйский горный хребет) их настигли бурные ветры. Многие участники похода получили увечья или пострадали от сильных холодов.