Свернув с побережья, экспедиция пошла в юго-западном направлении через угрюмые и безлюдные пустоши Чукотского нагорья, чтобы вернуться к Анадыри, заодно обследовав неизвестные земли. В конце июня во время перехода в горах, попавший в засаду отряд атаковали с двух сторон чукотские воины числом до 3 тыс. под командованием тойонов Хыпаю и Наихню. Павлуцкий скомандовал занять, говоря сегодняшним языком, «круговую оборону», поместив больных и раненых за ограждение из поставленных вплотную нарт. В завязавшемся ожесточенном бою, который длился полдня, русские и служивые аборигены отбили ружейным огнем все атаки многократно превосходивших их числом чукчей и затем поднялись в контрнаступление. Потеряв несколько сотен человек убитыми, чукчи бежали, при этом несколько их погибло от рук бросившихся в погоню за ними людей Павлуцкого. Окруженные воины, не желая быть схваченными русскими, прибегали к самоубийству. Людям Павлуцкого удалось взять в плен около десяти человек. Потери экспедиции составили двадцать человек ранеными. Пленные аборигены сообщили о местонахождении сорокатысячного стада оленей, которое экспедиция, найдя, тоже захватила.
После выздоровления раненых экспедиция, нагруженная трофеями, продолжила путь. В последний месяц лета 1731 г. у возвышенного мыса Сердце-Камень отряд подступил к стойбищу тойона Кею, под началом которого находилось около полутысячи воинов. Кею лично вышел к Павлуцкому и заявил о своем желании стать российским подданым и уплатить ясак. Капитан согласился ждать ясака до завтра. Однако назавтра ясака русские так и не дождались. Когда тойону напомнили о его обещании, чукчи неожиданно бросились на русских в атаку. В завязавшемся жестоком сражении, которое длилось всю вторую половину дня до вечера, чукчей было убито до двухсот человек, оставшиеся бежали во главе со своим тойоном. Отряд Павлуцкого потерял одного человека (из казаков) убитым и тридцать человек получили ранения. Нескольких чукчей русские пленили, к тому же забрали бывших в стойбище тридцать оленей. Среди убитых воинов Кею был обнаружен эскимос, его этническую принадлежность определили по прорезям в губе, откуда торчали надетые на зубы кости в виде моржовых клыков. Позже выяснилось, что чукчи Кею, поняв, что одними своими силами им с русскими не справиться, заключили союз с эскимосами острова Ратманова, не уступавшими им в выносливости, силе духа и боевом искусстве.
Следующим днем экспедиция подошла к самой горе Сердце-Камень. Здесь к русским пришли двое местных авторитетных людей Чимкаиган и Копенкин, которые, как позавчера Кею, заявили, что их роды согласны на уплату ясака, а в залог верности они сами готовы остаться у Павлуцкого. Однако, пока экспедиция несколько дней ждала обещанного ясака, жившие в окрестностях Сердце-Камня чукчи ушли в необъятные просторы тундр. Когда выяснилось, что местность опустела, Копенкин покончил с собой ударом ножа, а Чимкаиган сам попросил русских себя убить, как он объяснил, из-за обиды на своих родственников. Павлуцкий удовлетворил его просьбу. Скорее всего, мужчины просто хотели задержать продвижение экспедиции, чтобы их соплеменники смогли вовремя уйти со всем своим жизненно необходимым в тундре кочевым хозяйством.
От Сердце-Камня экспедиция вышла к реке Анадырь (ее устью) и осенью 1731 г. возвратилась в острог. Так был осуществлен первый поход на Чукотку Д. Павлуцкого. Поход длился восемь — десять (разные источники сообщают свои сроки) месяцев, в течение которых экспедиция прошла по суровой, холодной и скудной съестным тундре, через скалистое Чукотское нагорье около двух тысяч километров. По возвращении выяснилось, что половина отряда была больна, боевые потери составили девять — десять человек (3, возможно 4 казака; юкагир; 5 человек коряков), восемь человек умерли в пути от болезней, один потерялся в тундровых просторах. Потери чукчей составили, предположительно, несколько сотен воинов, что было, учитывая их общую численность в то время около десяти тысяч человек всего, серьезным ударом. Число убитых женщин и детей нигде конкретно не указывается. Около полутора сотен чукчей обоего пола, детей и взрослых, попали в плен.
Свыше сорока тысяч чукотских оленей, захваченных отрядом, почти полностью были отданы ясачным юкагирам и корякам под присмотр. Экспедиция смогла захватить обратно и оружие, попавшее в руки чукчей, и отрядное знамя А. Шестакова, а также личные вещи того. Были освобождены плененные чукчами сорок два коряка и русские — женщина и мужчина. В Анадырский острог также была привезена 141 лисья шкура.