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