В августе 1641 г. Дежнев вышел из Якутска в составе отряда из 16 казаков во главе с Михаилом Стадухиным с целью пройти на Оймякон, левый приток Индигирки, куда казаки прибыли уже глубокой осенью. Затем он в составе отряда побывал на р. Моме и спустился на коче к устью Индигирки. Осенью он вместе со Стадухиным перешел морем в устье Ала-зеи, где отряд Стадухина соединился с отрядом Зыряна и осенью 1643 г. направился также морем к устью Колымы.

Вероятнее всего, Дежнев принял активное участие в постройке Нижнеколымского зимовья, где он прожил три года и отличился храбростью при сборе ясака с местных племен. На Колыме среди казаков все шире распространялись слухи о том, что на востоке от бассейна Колымы течет « захребетная река Погыча», по берегам которой в тайге водится множество соболей. Доходили до казаков слухи и о наличии на востоке от Колымы моржовых лежбищ, что сулило богатую добычу « рыбьих зубов» ( моржовых клыков).

Все эти слухи стали известны и многим торговцам и промышленникам, которых немало собралось в Нижнеколымске. Федот Алексеев Холмогорец ( Попов) решил организовать крупную промысловую экспедицию для поиска этой таинственной р. Погычи ( с 1647 г. эту реку стали называть Анадырь).