Первым в этот район проник летом 1643 г. казачий десятник Василий Сычов. От Туруханска с отрядом он прошел на верхнюю Пясину, оттуда на Хету, по ней и Хатанге спустился к заливу и, скорее всего, сухим путем вышел на среднее течение реки Анабар. Он собирал ясак «в новой землице» и в верховьях реки до лета 1648 г. и вышел к устью реки, где встретил пришедшего ему «на перемену» Якова Семенова с партией стрельцов. Вместе они вернулись к зимовью и весь остаток года, а также зиму и весну 1649 г., передвигаясь на нартах и лыжах, потратили на поиски неясачных эвенков, поднимались по реке Удже, правому притоку Анабара, и по реке Уэле, причем открыли Оленьский хребет (хребет Прончищева) и ряд мелких «сторонних рек», то есть завершили открытие Северо-Сибирской низменности.

Поиски не увенчались успехом, и в середине мая 1649 г. землепроходцы перешли с реки Анабар на среднее течение реки Попигай (72° с.ш.). Здесь они что-то не поделили и разошлись – Сычов спустился к устью Попигая, а Семенов вернулся на Анабар. К этому времени – не позднее 1648 г. – с востока к Анабару морем от реки Оленек прошли и «енисейцы».

С 1646 г. особый интерес жителей Нижнеколымска вызывала неизвестная река Анадырь. Рассказывали, что эта река, прибрежные леса которой были якобы богаты соболем, находилась за горными хребтами и путь к ней лежал по Ледовитому морю. О снаряжении экспедиции для поисков Анадыря задумались не только в Нижнеколымском остроге, но и в Якутске. К лету 1647 г. в Нижнеколымском остроге была подготовлена экспедиция для поисков лежбищ моржа, для торговли с чукчами и открытия неведомой реки Анадырь. Во главе экспедиции стоял приказчик московских купцов Федот Алексеев(ич) Попов. В состав экспедиции, кроме Попова, входили 62 человека – 50 «своеужников», то есть промышленников, имевших собственное охотничье снаряжение («ужину»), и 12 «покрученников», не имевших собственного снаряжения, продовольствия и нанявшихся («покрутившихся») к Федоту Попову на условиях отдачи в его пользу 2/3 добычи.

Вероятно, для того чтобы получить государственную поддержку, Попов попросил власти Нижнеколымского острога включить в экспедицию служилого человека для сбора ясака. Узнав об этом, Семен Иванович Дежнев (около 1605–1673) подал челобитную с просьбой о назначении его в экспедицию, обязуясь представить в казну определенное количество пушнины. Ходатайство его было удовлетворено. В этой экспедиции Дежнев, как представитель государственной власти, сразу же занял руководящее положение. Свою задачу он видел в том, чтобы найти морской путь в неизвестные реки на востоке Сибири, в частности, в реку Анадырь, привести народности, живущие на берегах этих рек, в подданство Московского государства и обложить это население ясаком. Этим самым Дежнев брал на себя всю ответственность за успех экспедиции. Он по праву должен быть признан первым лицом в этом морском путешествии.

Летом 1647 г. четыре коча вышли из Нижнеколымского острога в море, чтобы «той кости рыбьего зуба и соболиных промыслов разведати». Море в районе устья Колымы в этом году оказалось покрытым тяжелыми, непроходимыми льдами, и к осени мореходы вынуждены были вернуться в Нижнеколымский острог.

Неудача не обескуражила искателей «рыбьего зуба». На следующее лето, 20 июня 1648 г., они направились в море уже на шести кочах. Дежнев и Попов по-прежнему были руководителями экспедиции.

К экспедиции самовольно присоединился седьмой коч, на котором находились «воровских людей человек с тридцать» под началом Герасима Анкудинова. Эта группа казаков преследовала исключительно корыстные цели и даже пыталась отстранить Дежнева от участия в экспедиции. Однако отказываться от таких спутников не стали – в таком предприятии каждый человек был на счету. Всего в это морское путешествие направилось 7 кочей, на которых находилось 90 человек.