Стадухин принял решение идти на Мому, спустившись вниз по Индигирке до ее устья, а затем идя на восток Северным Ледовитым океаном. Об этом решении казаки сообщали в той же челобитной. «А нынечи мы, холопи твои, впредь не хотя твои, государевы службы не отбить, и слышачи про ту реку и про те многие люди, и с того тунгускаво разорения пошли на ту реку Мому, и тей людей сыскивать…», Мому русские стали называть рекой Ковымой (Колымой).
Принялись за строительство коча. Добротного корабельного леса, ели и лиственницы, было вокруг предостаточно. Многие из поморов были искусными корабельными плотниками. Начальник отряда, отправлявшегося дальний поход, всегда старался предвидеть возможность строительства коча и запасался необходимым инструментом. Он также подбирал в свой отряд опытного корабельного мастера, который мог бы организовать строительные работы. Вероятно, такой мастер был и среди стадухинцев. Мастерили коч прочный, способный выдержать плавание по бурному океану, столкновение со льдинами. Парус шили из оленьих шкур, якорь изготовили из тяжелого лиственничного комля
И вот под дружные возгласы спустили просмоленный, проконопаченный коч на воду. Отряд из четырнадцати человек покинул негостеприимное, студеное зимовье. Небольшое судно спустилось по Оймякону и вышло в Индигирку. В верхнем течении эта река прорезала ряд поросших лесом горных хребтов. Неоднократно приходилось преодолевать пороги и перекаты. Ниже последних порогов река становилась шире и глубже, и, наконец, она входила в широкую заболоченную долину, растекаясь местами на рукава и образуя островки.
В низовьях Индигирки стадухинцам встретилось много казаков и промышленных людей. Среди них оказался отряд Дмитрия Зыряна. Он намеревался пойти с Индигирки морем на дальние реки, в земли неясачных юкагиров. Зырян оказался товарищем Дежнева по походу на Яну. Обрадовались встрече старые сослуживцы, вспомнили верхоянское зимовье.
Дмитрий рассказал о своем недавнем походе. Он ходил со своим отрядом на кочах на Алазею, прихватив с собой «вожа» (проводника) из юкагиров. Алазея впадает в Ледовитый океан несколько восточнее индигирского устья. Там произошла встреча отряда Зыряна с неясачными юкагирами, которые до этих пор никогда не видели русских и никому не платили дани. На Алазее же русские впервые увидели неведомый доселе народ - «чухчей», «чухоцких мужиков» (чукчей). Старания Дмитрия Зыряна объясачить местное население, призвать его «под государеву руку» встретили яростное сопротивление. Алазеи (один из юкагирских родов) окружили казачьи кочи, «учали нас стрелять», как сообщал начальник отряда. Значительная часть казаков пострадала от ранений стрелами. Все же русские отбили нападение, «алазеи от нас убегом ушли, избиты и изранены». Во время столкновения был убит алазейский князец Невгоча в числе других нападавших. Казаки захватили в плен одного из алазейских предводителей, «доброго мужика» Мамыка.