Путь от Якутска по долине р. Тумарх, притока Алдана, до перевала через Верхоянский хребет и далее на север в долину р. Дулгалах, одного из истоков Яны, был тяжелым. Через пять недель пути казаки добрались до Верхоянского зимовья, поставленного еще в 1638 г. при слиянии рек Дулгалаха и Сартанга, стекающих с Верхоянского хребта и образующих Яну.
На Яне отряд Зыряна собрал в качестве ясака 340 соболей и черно-бурых лисиц. Весной 1641 г. Зырян решил отправиться на реки, расположенные к востоку от Яны. А Дежнева с меховой казной в сопровождении трех казаков он отправил, вероятно, еще по зимнему пути в Якутск через Верхоянский хребет. Прознав о передвижении небольшой группы русских, кочевавшие там эвены, по словам самого Дежнева «40 ламуцких мужиков, а может и больше», устроили засаду. Внезапно атакованные казаки встретили нападавших «огненным боем». Дежнев метким выстрелом сразил предводителя нападавших, но сам был дважды ранен стрелой в левую ногу. После гибели предводителя нападавшие бежали. Меховая казна была доставлена в Якутск в целости и сохранности. Он и его спутники привезли в Якутск и принадлежащую им пушнину, которая по распоряжению письменнного головы Василия Пояркова была конфискована и возвращена только после подачи казаками челобитной на имя царя Михаила Федоровича.
В августе 1641 г. Дежнев вышел из Якутска в составе отряда из 16 казаков во главе с Михаилом Стадухиным с целью пройти на Оймякон, левый приток Индигирки, куда казаки прибыли уже глубокой осенью. Затем он в составе отряда побывал на р. Моме и спустился на коче к устью Индигирки. Осенью он вместе со Стадухиным перешел морем в устье Алазеи, где отряд Стадухина соединился с отрядом Зыряна и осенью 1643 г. направился также морем к устью Колымы.
Вероятнее всего, Дежнев принял активное участие в постройке Нижнеколымского зимовья, где он прожил три года и отличился храбростью при сборе ясака с местных племен. На Колыме среди казаков все шире распространялись слухи о том, что на востоке от бассейна Колымы течет «захребетная река Погыча», по берегам которой в тайге водится множество соболей. Доходили до казаков слухи и о наличии на востоке от Колымы моржовых лежбищ, что сулило богатую добычу «рыбьих зубов» (моржовых клыков).
Все эти слухи стали известны и многим торговцам и промышленникам, которых немало собралось в Нижнеколымске. Федот Алексеев Xолмогорец (Попов) решил организовать крупную промысловую экспедицию для поиска этой таинственной р. Погычи (с 1647 г. эту реку стали называть Анадырь).
Xолмогорец сумел снарядить четыре коча, на которых вышли в плавание 63 промышленника и торговца. Дежнев был по его просьбе включен в состав экспедиции в качестве официального лица, представителя московских властей, ответственного за сбор ясака в «новых землицах», получив наказную память на это от приказчика Нижнеколымского острога казака Второго Гаврилова. В своей отписке якутскому воеводе, датированной после июня 1647 г., Гаврилов докладывал: «В прошлом во 154 году (1646 г. — М.Ц.) летом с усть Ковымы реки ходили на море гуляти в коче вперед промышленные люди девять человек: Исайко Игнатьев Мезенец, Семейка Алексеев Пустозерец с товарищи. И с моря пришли к нам на Ковыму реку в роспросе сказали: бежали де они по большому морю, по зальду, подле Камень двои сутки парусом и доходили до губы, а в губе нашли людей (академик Л. С. Берг вполне обоснованно предполагает, что они достигли Чаунской губы. — М.Ц.), а называются чухчами, а с ними торговали небольшее место потому, что толмача у них не было, а съезжати к ним с судна на берег не смели, вывезли к ним товарцу на берег, положили и они в то место положили кости рыбья зуба немного а не всякой зуб цел; деланы у них пешни да топоры ис той кости, и сказывают, что на море де тово зверя много ложится де он на место. И в нынешнем во 155 году, июня… пошли на море москвитина гостиной сотни торгового человека Алексея Усова прикащик Федотко Алексиев холмогорец с покрученниками двенатцать человек (промышленники, снаряженные за счет Алексеева. — М.Ц.), а иные збирались промышленные люди своиуженники (промышленники, которые снарядились сами, за свой счет. — М.Ц.), а сверх их собралось 50 человек, пошли на четырех кочах той кости рыбья зуба и соболиных промыслов разведывати. И тот Федотко Алексиев с товарищи к нам в съезжую избу словесно прошали (просили выделить. — М.Ц.) с собою служилого человека. И бил челом государю Якуцкого острогу служилой человек Семейка Дежнев ис прибыли, а челобитную подал в съезжей избе, а в челобитной явил государю прибыли на новой реке в Анандыре сорок семь соболей (сороков — это 40 шкурок соболей, семь сороков — 280 шкурок. — М.Ц.). И мы его, Семейку Дежнева отпустили для тое прибыли с торговым человеком с Федотом Алексиевым и для иных новых рек проведывать и где бы государю мошно прибыль учинити. И дали им наказную память и где буде найдут неясашных людей, и им аманатов имати (брать заложников. — М.Ц.) и государев ясак с них збирати и под ево царскую высокую руку подводити и прочая» (31, с.110, 111).
Из наказной памяти следует, что Федор Алексеев Холмогорец был назначен целовальником, то есть отвечал за поступление в казну денежных доходов. А благодаря этому и наличию в составе экспедиции лица, ответственного за сбор ясака (С. И. Дежнев), сугубо частная экспедиция становится в определенной степени экспедицией, посланной колымскими властями.
Летом 1647 г. четыре коча вышли из Колымы в море и повернули на восток. Так и неизвестно, как далеко к востоку смогли они продвинуться. Из-за тяжелых ледовых условий экспедиция тем же летом возвратилась в Нижнеколымск.
Известный историк географических открытий русских землепроходцев Б. П. Полевой сообщил, что лишь в 1957 г. удалось обнаружить две ранее не известные челобитные С. И. Дежнева, из текста которых впервые выяснилось, что осенью 1647 г. он решил на следующий год возвратиться на Лену, а зиму 1647–1648 гг. провести на соболином промысле. В челобитной, поданной в Нижнеколымском зимовье колымскому приказчику Второму Гаврилову, Дежнев писал: «Яз, холоп твой, иду вверх по Ковыме для ради великие своея ножа (нужды. — М.Ц.).» (33, с. 26). Дежнев прошел в лесистую часть Средней Колымы и занимался там промыслом соболя. 28мая 1648 г. в Среднеколымском зимовье он уплатил в счет промысла 40 соболей десятую часть — 4 соболя. А на следующий день он приобрел у промышленника Сысолетина 13 соболей, и только в середине июня он начал продавать своих соболей, видимо после получения предложения от Гаврилова участвовать в новом походе на восток.
Дело в том, что, несмотря на неудачу, Попов решил повторить плавание на восток на следующий год. Когда Дежнев снова подал просьбу о назначении его в экспедицию 1648 г. ответственным представителем властей и сборщиком ясака, то на этот раз подобное предложение подал и якутский казак Герасим Анкидинов, который обещал собрать для казны 280 соболей и вдобавок поступить на «государеву службу своим животом, судном и оружьем, порохом и всякими заводы» (31, с.112), то есть снарядив за свой счет судно и приобретя таким же образом оружие, боеприпасы и все необходимое снаряжение.
Дежнев в свою очередь обещал увеличить сбор ясака до 290 соболей и обвинил Анкидинова в том, что тот «прибрал к себе воровских людей человек с тридцать, и хотят оне торговых и промышленных людей побивати, которые со мною идут на ту новую реку, и животы их грабить, иноземцев хотят побивать же, с которых я прибыль явил» (31, с.113). Колымские власти поддержали Дежнева и назначили его вновь своим официальным представителем. Тогда один из подчиненных Анкудинова Пятко Неронов подал Гаврилову жалобу на Дежнева, обвиняя его в незаконных действиях и требуя над ним «царского суда». Но Гаврилов, убедившись в абсолютной голословности обвинений, проигнорировал жалобу. Тем не менее Анкидинов со своими людьми снарядил коч и сумел присоединиться к экспедиции Попова—Дежнева.
Б. П. Полевой считает, что плавание новой экспедиции началось из Среднеколымского зимовья 20 июня. После остановки в Нижнеколымском зимовье экспедиция вышла в Ледовитое море в начале июля (33, с.26)
Помимо Федота Алексеева и его 29 покручеников, в походе приняли участие приказчики богатого московского гостя Василия Гусельникова Афанасий Андреев и Бессон Астафьев со своими покручениками. Эти приказчики возглавляли отдельный отряд, разместившийся на двух или трех кочах.
Дежнев в экспедиции непосредственно возглавил один из отрядов, составивший экипаж одного коча. Отряд состоял из 18 промышленных и служилых людей. В снаряжении этого отряда он принял личное участие. Впоследствии он указывал в челобитной, что снарядился для похода к Анадырю «на свои деньги» и «от морского разбою (кораблекрушений во время бури. — М.Ц.) обнищал и одолжал великими неокупными долги» (36, с.178). Видимо, он вложил в снаряжение экспедиции все свои деньги, полученные за продажу большой партии соболей, вымененных на русские товары и полученных в результате удачной охоты во время промысловых поездок на Колыме.