Осенью 1640 г. Дежнев был послан для усмирения мятежного якутского князца Сахея Отнакова. Еще летом 1640 г. несколько родов в центральной Якутии, недовольных большим ясачным обложением, осадили Якутск. Не сумев выбить русских из острога, князцы в конце концов вынуждены были заключить мирное соглашение с якутскими властями и согласились платить ясак. Но несколько князцов-тойонов и в том числе Сахей не замирились. Посланные к нему два сборщика ясака были убиты, а затем Сахей со своим родом откочевал в дальнюю Оргутскую волость на Среднем Вилюе. Посланный против Сахея отряд попал в засаду и понес тяжелые потери.
После этого якутские власти и послали Семена Дежнева для умиротворения непокорного князца и получения ясака. Подробности похода Дежнева против непокорного Сахея до нас не дошли. Известно, что отряд Дежнева возвратился в Якутск без потерь, доставив в Якутск сполна взысканный с Сахеева рода ясак — 140 соболей. Значит, и в этот раз Дежнев использовал, вероятнее всего, какие-то мирные средства для замирения князца, возможно он только постарался припугнуть Сахея, а затем наладил с ним добрые отношения, не провоцируя якутов на оказание сопротивления казачьему отряду.
Затем Дежнев был включен в состав отряда Дмитрия Михайлова Зыряна (Ярило), который с наступлением зимы отправился из Якутска на конях через Верхоянский хребет на р. Яну. Причем лошадей и все необходимое снаряжение Дежнев купил за собственные деньги. Позже в 1662 г. он напишет в челобитной по этому поводу: «И я, холоп твой, для твоей государевой службы купил две лошади, дал 85 рублев, и платьишко, и обувь и всякий служебный завод, покупаючи в Якутском остроге у торговых и у промышленных людей дорогою ценою: стал подъем мне, холопу твоему, больши сто рублев» (36, с.131). При годовом окладе рядового казака 5 рублей ясно, что, вероятнее всего, Дежнев в предыдущие два года не только собирал государев ясак, но и выменивал у якутов шкурки на пользовавшиеся спросом товары. Не исключено и то, что он в ходе походов по заданиям властей находил возможность охотиться на соболя.
Путь от Якутска по долине р. Тумарх, притока Алдана, до перевала через Верхоянский хребет и далее на север в долину р. Дулгалах, одного из истоков Яны, был тяжелым. Через пять недель пути казаки добрались до Верхоянского зимовья, поставленного еще в 1638 г. при слиянии рек Дулгалаха и Сартанга, стекающих с Верхоянского хребта и образующих Яну.
На Яне отряд Зыряна собрал в качестве ясака 340 соболей и черно-бурых лисиц. Весной 1641 г. Зырян решил отправиться на реки, расположенные к востоку от Яны. А Дежнева с меховой казной в сопровождении трех казаков он отправил, вероятно, еще по зимнему пути в Якутск через Верхоянский хребет. Прознав о передвижении небольшой группы русских, кочевавшие там эвены, по словам самого Дежнева «40 ламуцких мужиков, а может и больше», устроили засаду. Внезапно атакованные казаки встретили нападавших «огненным боем». Дежнев метким выстрелом сразил предводителя нападавших, но сам был дважды ранен стрелой в левую ногу. После гибели предводителя нападавшие бежали. Меховая казна была доставлена в Якутск в целости и сохранности. Он и его спутники привезли в Якутск и принадлежащую им пушнину, которая по распоряжению письменнного головы Василия Пояркова была конфискована и возвращена только после подачи казаками челобитной на имя царя Михаила Федоровича.
В августе 1641 г. Дежнев вышел из Якутска в составе отряда из 16 казаков во главе с Михаилом Стадухиным с целью пройти на Оймякон, левый приток Индигирки, куда казаки прибыли уже глубокой осенью. Затем он в составе отряда побывал на р. Моме и спустился на коче к устью Индигирки. Осенью он вместе со Стадухиным перешел морем в устье Алазеи, где отряд Стадухина соединился с отрядом Зыряна и осенью 1643 г. направился также морем к устью Колымы.
Вероятнее всего, Дежнев принял активное участие в постройке Нижнеколымского зимовья, где он прожил три года и отличился храбростью при сборе ясака с местных племен. На Колыме среди казаков все шире распространялись слухи о том, что на востоке от бассейна Колымы течет «захребетная река Погыча», по берегам которой в тайге водится множество соболей. Доходили до казаков слухи и о наличии на востоке от Колымы моржовых лежбищ, что сулило богатую добычу «рыбьих зубов» (моржовых клыков).
Все эти слухи стали известны и многим торговцам и промышленникам, которых немало собралось в Нижнеколымске. Федот Алексеев Xолмогорец (Попов) решил организовать крупную промысловую экспедицию для поиска этой таинственной р. Погычи (с 1647 г. эту реку стали называть Анадырь).