Купеческий караван, ведомый известным землепроходцем и мореходом Иваном Ребровым, благополучно прибыл на р. Оленек. Однако надежды Федота на удачные торговлю и промысел не оправдались. Местные эвенки восстали и вытеснили торговцев и промышленников из лесов, где водился соболь, в тундру. Видимо, не удалось Федоту наладить меновую торговлю с местными жителями. Сопротивление местных племен заставило русских промышленников временно перейти на другие реки. Вероятнее всего, с ними ушел и Федот Алексеев. Пришлось ему перебраться на Лену, а оттуда и на расположенные к востоку северные реки. Зимой или весной 1647 г. он прибыл на Колыму, где собирался покрыть убытки, понесенные на оленекских промыслах. Именно на Колыме он встретил Семена Дежнева, и далее их жизненные дороги некоторое время шли рядом.

Судьба Семена Дежнева во многом была типичной для сибирского казака того времени. Наиболее вероятно, что родиной его является Поморский край, где он родился около 1605 г. в деревне Осиновская Волоко-Пинежской волости Двинского уезда. Там Дежневы имели свою землю и в начале ХVІІІ в.

С. И. Дежнев по примеру многих поморян связал свою жизнь с Сибирью, где уже в молодые годы, видимо не позже 1630 г., начал казачью службу сперва в Тобольске, а затем в Енисейске. В 1638 г. он был направлен на службу в Якутск в составе казачьего отряда сотника Петра Бекетова. Вместе с ним на службу в Якутск из Енисейска пришли Михайло Стадухин, Василий Бугор, Постник Иванов и другие казаки, чьи имена навсегда вошли в историю русских географических открытий в Сибири и на Дальнем Востоке.

По прибытии в Якутск Дежнев был поставлен на денежное, хлебное и соляное довольствие с окладом рядового казака. Как и многие из сибирских казаков, С. И. Дежнев был женат, видимо, дважды и оба раза на якутках. Наверное, он говорил по-якутски. В 1639–1640 гг. Дежнев участвовал в походах для сбора ясака у местных жителей якутских волостей.

У сибирских казаков в те времена было принято сочетать службу с собственным промыслом. В «Книге покупочной» Якутского острога сохранилась запись, относящаяся к 1638 или началу 1639 г., — «Куплено у служилого Семейки Дежнева 4 соболя без хвостов, дано государевы муки 12 безмен» (36, с.111). В первый же сезон пребывания на Лене Дежнев собрал в качестве ясака 100 соболей, больше, чем другие его сослуживцы.

В середине 1640 г. он с двумя казаками был направлен на реки Татту и Амгу, левые притоки Алдана, для замирения непокорных якутов, нападавших на мирных якутов, аккуратно сдававших ясак. Ограбленные пожаловались на эти нападения якутским властям. Быстрое возвращение Дежнева в Якутск, видимо, связано с успешным выполнением порученного задания без применения к виновникам силовых действий. Следует отметить, что Дежнев на протяжении всей службы всегда старался действовать мирными средствами, применяя силу лишь в крайнем случае.

Осенью 1640 г. Дежнев был послан для усмирения мятежного якутского князца Сахея Отнакова. Еще летом 1640 г. несколько родов в центральной Якутии, недовольных большим ясачным обложением, осадили Якутск. Не сумев выбить русских из острога, князцы в конце концов вынуждены были заключить мирное соглашение с якутскими властями и согласились платить ясак. Но несколько князцов-тойонов и в том числе Сахей не замирились. Посланные к нему два сборщика ясака были убиты, а затем Сахей со своим родом откочевал в дальнюю Оргутскую волость на Среднем Вилюе. Посланный против Сахея отряд попал в засаду и понес тяжелые потери.

После этого якутские власти и послали Семена Дежнева для умиротворения непокорного князца и получения ясака. Подробности похода Дежнева против непокорного Сахея до нас не дошли. Известно, что отряд Дежнева возвратился в Якутск без потерь, доставив в Якутск сполна взысканный с Сахеева рода ясак — 140 соболей. Значит, и в этот раз Дежнев использовал, вероятнее всего, какие-то мирные средства для замирения князца, возможно он только постарался припугнуть Сахея, а затем наладил с ним добрые отношения, не провоцируя якутов на оказание сопротивления казачьему отряду.

Затем Дежнев был включен в состав отряда Дмитрия Михайлова Зыряна (Ярило), который с наступлением зимы отправился из Якутска на конях через Верхоянский хребет на р. Яну. Причем лошадей и все необходимое снаряжение Дежнев купил за собственные деньги. Позже в 1662 г. он напишет в челобитной по этому поводу: «И я, холоп твой, для твоей государевой службы купил две лошади, дал 85 рублев, и платьишко, и обувь и всякий служебный завод, покупаючи в Якутском остроге у торговых и у промышленных людей дорогою ценою: стал подъем мне, холопу твоему, больши сто рублев» (36, с.131). При годовом окладе рядового казака 5 рублей ясно, что, вероятнее всего, Дежнев в предыдущие два года не только собирал государев ясак, но и выменивал у якутов шкурки на пользовавшиеся спросом товары. Не исключено и то, что он в ходе походов по заданиям властей находил возможность охотиться на соболя.

Путь от Якутска по долине р. Тумарх, притока Алдана, до перевала через Верхоянский хребет и далее на север в долину р. Дулгалах, одного из истоков Яны, был тяжелым. Через пять недель пути казаки добрались до Верхоянского зимовья, поставленного еще в 1638 г. при слиянии рек Дулгалаха и Сартанга, стекающих с Верхоянского хребта и образующих Яну.

На Яне отряд Зыряна собрал в качестве ясака 340 соболей и черно-бурых лисиц. Весной 1641 г. Зырян решил отправиться на реки, расположенные к востоку от Яны. А Дежнева с меховой казной в сопровождении трех казаков он отправил, вероятно, еще по зимнему пути в Якутск через Верхоянский хребет. Прознав о передвижении небольшой группы русских, кочевавшие там эвены, по словам самого Дежнева «40 ламуцких мужиков, а может и больше», устроили засаду. Внезапно атакованные казаки встретили нападавших «огненным боем». Дежнев метким выстрелом сразил предводителя нападавших, но сам был дважды ранен стрелой в левую ногу. После гибели предводителя нападавшие бежали. Меховая казна была доставлена в Якутск в целости и сохранности. Он и его спутники привезли в Якутск и принадлежащую им пушнину, которая по распоряжению письменнного головы Василия Пояркова была конфискована и возвращена только после подачи казаками челобитной на имя царя Михаила Федоровича.

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

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

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