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

Примеру Василия Бугра и Евсевия Павлова последовали и их товарищи по скитаниям, среди них беглый казак Шалам Иванов, вскоре смертельно раненный в схватке с ходынцами на вершине Анюя. К отряду Моторы и Дежнева присоединились и другие беглые казаки, бывшие стадухинцы, и в их числе Никита Семенов, Павел Кокулин. Это пополнение компенсировало те потери, которые отряд понес минувшей осенью.

А дальнейшая судьба Стадухина была такова. Ему успешно удалось достичь той цели, которую не смогли достичь Мотора с Дежневым. С поредевшей ватагой он перевалил через горы и вышел на Пенжнну, очевидно, с помощью местного проводника. Этот поход можно считать предысторией проникновения русских на Камчатку сухопутной дорогой. Мы видели, что первыми русскими, попавшими на Камчатский полуостров, были люди из отряда Федота Алексеева, но они достигли этого края морем. Местные обитатели, коряки, заселявшие долину Пенжины, как и Олюторский полуостров и север Камчатки, встретили небольшой русский отряд недоверчиво. Вероятно, не раз вспыхивали вооруженные столкновения. Не рассчитывая закрепиться на Пенжине со своими слабыми силами и опасаясь коряцких нападений, Стадухин принял решение идти дальше. Его люди построили суда и морем перешли в устье соседней реки, Гижиги. Переход с Пенжины на Гижигу занял три дня. Но и там не миновала опасность нападений на отряд со стороны коряцких племен, довольно многочисленных. Тогда Стадухин покинул Гижигу и в конце концов достиг устья небольшой реки Тоуй, впадавшей в Охотское море, и там построил острожек. Оттуда русские совершали вылазки для объясачивания местного населения и сбора ясака.

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

В течение шести лет воеводская администрация не получала никаких сведений о Стадухине. Полагали, что он погиб — то ли утонул, то ли замерз на горном перевале, то ли пал в стычке с каким-нибудь воинственным племенем. Но Михаиле в конце концов дал о себе знать. Летом 1657 года стадухипский отряд вышел по побережью Ламского (Охотского) моря к Охотскому острогу с богатой ясачной казной, собранной с коряков и эвенов. Через два года Стадухин вернулся в Якутск.

Личность Михаилы Стадухииа нельзя оценивать однозначно. Это был сын своего века, дерзкий, отважный, решительный, с крутым нелегким характером, доставлявший своим сослуживцам немало тягот. Он мог обидеть слабейшего, ограбить товарища. В основе его вражды с Дежневым лежало непомерное честолюбие, стремление первенствовать. Но пусть эти дурные черты его характера не заслоняют в нем отважного первопроходца. Он и Семен Мотора были первыми русскими, которые прошли сухопутной дорогой с Колымы на Анадырь. Стадухину принадлежит честь первооткрывателя рек Пенжины и Гижиги. Вслед за ним, в 1651 году на Гижигу с Колымы отправился с отрядом «охочих людей» Иван Баранов. Открытиями Стадухина и Баранова воспользовались русские первопроходцы, достигшие Камчатки сухим путем через Гижигу и Пенжину. Говоря о смелых подвигах и заслугах Федота Алексеева и Семена Дежнева, мы не должны забывать о Михаиле Стадухине, Василии Бугре, Семене Моторе, Юшке Селиверстове и многих других замечательных людях того времени, вносивших общий вклад в дело исследования и освоения Северо-Восточной Сибири.

Уход Стадухина на Пенжигу разрядил напряженную обстановку на Анадыри. Теперь люди не опасались разбойных нападений стадухинцев. Наладились отношения и с местным населением. Руководители отряда принимают решение спуститься вниз по реке и тщательно обследовать устье, лиман и прилегающие берега Анадырского залива. Если Анадырь бедна соболем и другим пушным зверем, то не порадует ли побережье моря лежбищами морского зверя? Не удастся ли наладить там промысел «рыбьего зуба», иначе говоря, моржовой кости, которую так ценят и в Якутске, и в далекой российской столице? У аборигенов края русские могли видеть разные украшения из моржовой кости. Стало быть, моржи здесь водятся.

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

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

Соорудив кочи, Дежнев с товарищами спустились вниз по Анадыри, когда река очистилась от льда. Они обследовали не только устье реки и лиман, но и ближайшие берега Анадырской залива и были поражены обилием морского зверя. Но самое ценное открытие заключалось в обнаружении большого морского лежбища на одной из отмелей. Здесь копошились бурые бугристые туши животных с клыкастыми усатыми мордами. Стадо испускало оглушительный рев, напоминавший то собачий лай, то коровье мычание. При приближении кочей с людьми рев усиливался, животные настороженно вглядывались зоркими круглыми глазами в непрошеных пришельцев. Некоторые безопасности ради семенили к кромке берега, неуклюже переваливаясь с боку на бок и тяжело плюхались в воду. Отдельные особи должно быть, старые самцы, достигали внушительных размеров — четырех и более метров. Поморы знали что на берегу морж неуклюж и опасности для человека не представляет. Но встреча промысловой лодки с разъяренными моржами, особенно ранеными в открытом море чревата опасными последствиями. Крепкие моржовые клыки могут легко пробить борт лодки.