Пройдя за месяц по тундре свыше 300 вёрст, только 2 марта севернее устья реки Анадырь отряд Павлуцкого настиг первые кочевья чукчей. От пленных узнали места стойбищ «главного тоена Тентиона» — их нагнали и разгромили через две недели где-то севернее современного чукотского посёлка Канчалан.
В битве погибли 106 чукотских воинов во главе с самим тойоном Тентионом. Его жена умерла от пыток — как описывалось в донесении Павлуцкого, «по распросам на огне зжена», русскому отряду требовалось добыть информацию о других чукотских кочевьях. Один же из маленьких сыновей Тентиона позднее вместе с другими пленными попал в Якутск, там его вырастила жена Павлуцкого, в крещении мальчик получил имя Николая и позднее стал известным исследователем Крайнего Севера, получил чин русского офицера и дворянское звание.
Но вернёмся в 1744 год, когда отряд Павлуцкого двигался по Чукотке на север вдоль берегов залива Креста, громя найденные кочевья и стойбища. Здесь были разгромлены яранги тойона Тегрувья и захвачены его табуны оленей. В конце мая разгромили огромное по местным меркам поселение береговых «пешихх чюкоч», в бою погибло 130 чукотских воинов.
По русским описаниям это был «острог, выкладенной ис каменьев». Сами чукчи такие укрепления называли Гуйвиир, «каменная крепость». В обороне своих «крепостей» у чукчей было одно слабое место — они непоколебимо верили, что враг никогда не войдёт в их яранги и землянки, так как побоится мести духов-покровителей, которые по их поверьям имелись у каждого северного жилища. Действительно, в междоусобных столкновениях ни чукчи, ни коряки, ни ительмены-камчадалы, все свято верившие в духов жилищ, никогда не врывались в жильё противника, они или вынуждали защитников разными способами покинуть его, или стремились его разрушить.
Но в столкновениях с русскими наивная тактика — засесть в своей яранге и не выходить из неё — не работала. Солдаты и казаки чукотских духов боялись меньше, чем начальства, и во время штурмов смело врывались в чукотские жилища, либо расстреливали их из ружей. К тому же при штурме таких «крепостей» русские с успехом использовали высокотехнологичное для тех лет оружие, которого точно никогда не было у их северных противников — ручные пороховые гранаты.
Защитить от русских свои посёлки, даже хорошо укреплённые, чукчи не могли. Помня об итогах прежних столкновений, они отныне избегали и открытого боя, лишь изредка беспокоя русских мелкими нападениями на обоз и табуны оленей. Павлуцкий рассылал в разные стороны дозорные отряды, но найти «главное чукотское войско», растворившееся в бескрайних пустынях Севера так и не смогли.
В начале лета 1744 года русский отряд вышел к берегам залива Лаврентия, самой крайней точке Чукотки на востоке. Отсюда повернули на запад, двигаясь вдоль берегов Восточно-Сибирского моря до устья реки Амгуэма, протекающей на севере Чукотки. Здесь пришлось повернуть на юго-запад и возвращаться в Анадырский острог, так как войско Павлуцкого уже испытывало голод.
Слишком большому по меркам Крайнего Севера отряду в походе, растянувшемся даже не на сотни, а на тысячи вёрст, было тяжело прокормиться. Вместо поиска неуловимых «чюхч», пришлось заниматься охотой на птиц и диких оленей, специально посылать отряды на побережье для добычи моржей и нерп и даже прибегнуть к «подножному корму». «Идучи по тундре питались травой и кореньем», — так позднее докладывал майор Павлуцкий начальству.
Отряд двигался медленно — были съедены почти все «езжалые» олени из обоза, приходилось часто останавливаться для поисков и добычи еды. От голода и дальних переходов многие обессилели, их пришлось нести на носилках, сделанных из копий и ремней. Чукчи шли по пятам уходящего отряда Павлуцкого и сумели убить нескольких казаков, отделившихся для рыбной ловли.
Лишь 22 сентября 1744 года отряд Павлуцкого вернулся в Анадырский острог. Пройдя за 8 месяцев в тяжелейших условиях по землям Чукотки почти 3000 км, так и не удалось решить главную задачу — уничтожить основные силы чукчей. Добыча так же оказалась ничтожной — не было ни ценных мехов, ни больших стад трофейных оленей, а из сотни взятых «в полон» женщин и детей большинство умерли от голода по дороге в Анадырский острог.
В отправленном начальству донесении майор Павлуцкий меланхолично доложил, что чукчи подчиняться не желают и «до последней капли крови намерены ратитца», поэтому необходимо продолжить походы в самые отдалённые края Чукотки. Однако на следующий год выступить не удалось — банально не хватило еды. Почти 500 человек в Анадырском остроге, помимо постоянного гарнизона, за зиму съели всех окрестных оленей. Лето 1745 года людям Павлуцклого пришлось полностью посвятить добыче и заготовке пропитания. Благодаря предусмотрительности майора удалось лишь перехватить один крупный отряд чукчей, отправившихся в очередной набег на байдарках по реке Анадырь.
Лишь в марте 1746 года неутомимый Павлуцкий вновь отправился в поход. На этот раз 250 солдат и казаков, вместо со 150 юкагирами и коряками, шли прямо на север к «Колымскому морю», как тогда русские именовали восточную честь Северного Ледовитого океана. В апреле отряд вышел к Чаунской губе на крайнем севере Чукотке, где уничтожил крупное стойбище береговых чукч.
Вскоре русские сами едва не погибли, но не от ударов противника, а под натиском природной стихии — не смотря на апрель, начался страшный снежный ураган, продолжавшийся более 5 суток. Выжив в катаклизме, который опасен даже для современной техники, отряд Павлуцкого продолжил поход, уничтожив еще одно поселение. Чукчи, видя превосходство неприятеля, прежде чем погибнуть в бою, по традиции убили свои семьи, чтобы они не попали в плен. Как позднее писал в докладе Павлуцкий — «не хотя итти в покорность, тако ж джен и детей своих прикололи…»
Найти другие стойбища и кочевья чукчей больше не удалось, и к лету 1746 года отряд Павлуцкого вернулся в Анадырский острог. Трофеи вновь были минимальны — четверо пленных и семь сотен оленей. Оставшуюся часть тёплого сезона русским вновь пришлось посвятить добыче пропитания, дабы пережить долгую полярную зиму.
Стратегия дальних походов по бескрайним и пустынным пространствам Чукотки зашла в тупик. Впрочем, майору Дмитрию Павлуцкому ходить в них больше не пришлось — весной следующего 1747 года чукчи его убили.
12 марта 1747 года на берегу реки Майн (Мэйнывээм— по-чукотски «большая река», правый приток Анадыри), совсем близко по северным меркам от Анадырского острога, крупный отряд чукчей, напав на коряков, взял в плен 8 человек и угнал семь оленьих табунов. Среди угнанных оленей были и предназначенные для прокорма гарнизона Анадырского острога.
В тот же день, узнав о нападении, майор Павлуцкий бросился в погоню. Собирались экстренно, вышли в ночь на 13 марта — 97 русских и 35 коряков на всех собачьих и оленьих упряжках, которые удалось собрать в остроге, двинулись по следу чукчей. За ними пешим порядком выступили те, кому не хватило упряжек — 202 солдата и казака под командованием сотника Алексея Котковского.
Передовой отряд Павлуцкого шёл на юг, по берегу реки Майн, именно здесь проходил «тракт», путь из Анадырского острога на Камчатку к Охотскому морю. Чукчей настигли утром 14 марта там, где в Майн впадает речка Орловая — в тополиных рощах по её берегам, действительно, гнездились орлы. Здесь на горе, ныне известной как Юкагирская сопка, отряд Павлуцкого и обнаружил грабителей — их оказалась целая армия, почти 600 чукотских воинов в костяной броне.
Павлуцкий, не смотря на такое неравенство в силах, приказал готовиться к атаке. В русском отряде возник короткий спор — часть казаков и корякские «князцы» просили майора дождаться идущие следом две сотни Котковского, другие считали, что надо атаковать, пока чукчи не ушли и не растворились в бескрайних снегах Чукотки. Позднейшее расследование Сената Российской империи зафиксировало прозвучавшие в те минуты слова казачьего сотника Семёна Кривогорницына: «Наши казаки воисты дома, а в виду неприятеля трусливы; теперь-то и бить злодеев, пока они в куче, а где их сыщем, когда разбредутся по загорьям?»
Похоже, Павлуцкий и его люди за последние годы устали от многомесячных и бесплодных попыток искать «настоящих людей» посреди безжизненной тундры. Здесь и сейчас противника не надо было искать — основные ударные силы чукотских родов наконец стояли перед ними в полной боевой готовности. И 97 русских атаковали шесть сотен неприятеля.
Люди Павлуцкого двинулись вверх по сопке. Согласно дошедшим до нас воспоминаниям, сильный ветер бросал в лицо русским колючий весенний снег, «что неприятелю много способствовало». Чукчи атаковали с горы — казаки и солдаты дали залп из ружей и единственной имевшейся при отряде небольшой железной пушки. Чукчи, уже опытные в боях с русскими, упали в снег и большая часть картечи с пулями просвистели над их головами. На второй залп у русских времени уже не осталось — несшаяся с горы масса костяной брони ударила в их отряд.
Началась рукопашная схватка. Сразу же сказалось численное преимущество чукчей, но русский отряд — уступавший противнику по количеству воинов, минимум, в пять раз — дрался упорно. По воспоминаниям выживших, свалка была такой плотной, «что неприятель у россиян ружья, копья, а россиане у неприятеля луки и копья ж отнимали руками и оборонялись ножами».
Русский отряд с боем и большими потерями отступил к подножию Юкагирской сопки, где укрылся от атак чукотских воинов за укреплениями, наспех построенными из саней. Позднее от пленных чукчей узнали подробности гибели майора Павлуцкого — при отступлении отряда он долго отбивался в окружении врагов, рубя саблей костяные наконечники их копий. Чукчи пытались расстреливать его из луков почти в упор, но майор в стальной кольчуге и шлеме был только ранен. С трудом чукчи свалили его арканами и добили ударом копья в горло.
Битва продолжалась пока на горизонте не появились несколько десятков передовых человек из спешившего следом отряда сотника Котковского. Завидев идущее к русским подкрепление, чукчи тут же прекратили атаки и на оленьих упряжках скрылись за горизонтом — «ушли в свою землиц