Центр русской колонизации первобытных земель Дальнего Востока в то время находился в Якутске, сообщение осуществлялось в основном по рекам: на судах-дощаниках летом и на санях по речному льду зимой. В 1725 г. якутский казачий голова (комендант) Афанасий Шестаков приехал в Петербург и представил вице-адмиралу П. Сиверсу доклад о Сибири, Камчатке и Японских островах, приложив к нему карту северо-востока Сибири, составленную на основании данных русских путешественников и рассказов местного населения. Он сообщил о существовании обширных еще не исследованных русскими земель и племенах, не обложенных ясаком. Очевидно, честолюбивый казачий голова рассчитывал на финансирование из государственной казны новой военно-исследовательской экспедиции, в которой начальником должен был стать он сам, а затем, после укрепления российского влияния на Камчатке и чукотских землях, занять должность их наместника. Заметки сибирского казачьего головы не могли не заинтересовать высших царских сановников. П. Сиверс рекомендовал А. Шестакова президенту Военной коллегии и фактическому правителю России при мало вникавшей в государственные дела императрице Екатерине I генерал-фельдмаршалу А. Меншикову. Через того предложение об организации сильной экспедиции для полного присоединения к России крайнего северо-востока Азии поступило на рассмотрение высших совещательных органов империи Правительствующего Сената и Верховного Тайного Совета.
Собранная властями экспедиция состояла из четырехсот казаков под непосредственным командованием капитана Тобольского драгунского полка Дмитрия Павлуцкого, нескольких научных специалистов и восемнадцати моряков, набранных для предстоящих плаваний по Охотскому морю. А. Шестакову было присвоено звание «главного командира северо-восточного края», и в июне 1727 г. экспедиция во главе с ним отправилась в Сибирь. По пути между Шестаковым — сыном простого казака, получившего дворянство за выслугу, и командиром казаков Павлуцким — потомком белорусских шляхтичей, возникли разногласия по поводу разграничения полномочий, в конечном итоге приведшие к конфликту. В результате экспедиция разделилась: Д. Павлуцкий из Якутска с 207 казаками двинулся в Анадырский острог по реке Лене, а А. Шестаков с оставшимися казаками и другими участниками экспедиции отправился в городок Охотск, чтобы следовать в земли коряков морским путем. 30 сентября 1729 г. корабль с экспедицией Шестакова прибыл в Тауйскую крепость, а 17 ноября собранный «командиром северо-восточного края» военный отряд, большей частью состоявший из аборигенов Сибири на русской службе, выступил на реку Пенжин собирать ясак с коряков.
Грубые действия и насилие А. Шестакова, который вел себя в отношении местного населения как самовластный диктатор, привели к выступлениям коряков и прекращению выплаты ими ясака. В феврале 1730 г. коряки на реке Гижиге атаковали отряд Шестакова; были убиты два казака. Однако сопротивление «инородцев» было безжалостно подавлено. Одновременно коряков продолжали беспощадно грабить чукчи, доводя их кочевья до совершенного разорения. Из-за их набегов коряки не могли платить ясак. В 1730 году чукчи, по данным служилых людей Анадырского острога, убили до сотни коряков-оленеводов. Те стали просить русских защитить их, даже предлагали свою помощь для войны с опасными соседями. Ирония жизни заключалась в том, что местная «тундровая великодержавность» чукчей столкнулась с великодержавными устремлениями Российской империи, власти которой действовали в обычном духе европейской колониальной политики того времени.