Летом 1647 года приказчик московских купцов Федот Алексеев Попов, родом из Холмогор, организовал поход для поисков моржовых лежбищ, для торговли с чукчами и для поисков морского пути к реке Анадырь, о богатстве которой промысловым зверем в Нижне-Колымск доходило немало слухов. Попов просил нижнеколымские власти о назначении в экспедицию служилого человека – представителя государственной власти – для приведения местного населения в русское подданство и сбора ясака. Узнав об этом, Дежнев подал челобитную о своем назначении в этот поход. Его ходатайство было удовлетворено, и, таким образом, Дежнев стал ведущим лицом в намечавшемся предприятии.
В тот же год отряд Дежнева-Попова вышел из Нижне-Колымска в море на четырех кочах, но из-за трудных ледовых условий осенью этого года вернулся обратно. Несмотря на неудачу, 3 июля (20 июня) 1648 года в новый поход на реку Анадырь из Нижне-Колымска вышло уже семь кочей, на которых находилось свыше ста человек. Шесть кочей входили в отряд Дежнева-Попова. Седьмой коч под командой Герасима Анкудинова присоединился к отряду самовольно. Во время этого похода состояние льдов у берегов Чукотки было очень благоприятно, и кочи, пользуясь попутными ветрами, быстро продвигались на восток. Не доходя Берингова пролива, два коча разбились о льды, а два пропали без вести. Крайнюю северо-восточную оконечность Азии, которую Дежнев назвал Большим Каменным Носом, обогнули только три коча – Дежнева, Попова и Анкудинова.
Большой Каменный Нос, ныне называемый мысом Дежнева, Дежнев описал следующими, совершенно бесспорными словами: “… А с Ковыми реки итти морем на Анадыр реку, и есть нос, вышел в море далеко… а против того носу есть два острова (острова Гвоздева), а на тех островах живут чухчи, а врезываны у них зубы, прорезываны губы, кость рыбей зуб, а лежит тот нос промеж сивер на полуношник, а с Русскою сторону носа признака: вышла речка, становье тут у Чухоч делано, что башни, из кости китовой, и нос поворотит кругом, к Онандыре реке подлегло”. У Большого Каменного Носа коч Анкудинова во время бури разбился. Анкудинов и его команда перебрались на кочи Дежнева и Попова.
После недолгой стоянки и высадки на берег в Беринговом проливе кочи пошли на юг. Вскоре и эти кочи разлучились. Коч Дежнева понесло на юго-запад и в октябре выбросило на берег значительно южнее устья Анадыря – невидимому на Олюторский полуостров. Отсюда Дежнев с 24 спутниками через 10 недель добрался до устья Анадыря. Во время зимовки многие умерли и к весне 1649 г. партия Дежнева уменьшилась до 12 человек. На лодках Дежнев со своими товарищами поднялся вверх по Анадырю и в среднем его течении построил Анадырский острог.
