По решению Сената для «призыва в подданство» коряков и чукчей, обследования и присоединения к русским владениям новых земель в Тихом океане в июне 1727 г. из Петербурга направилась экспедиция, возглавляемая якутским казачьим головой (полковником) Афанасием Федотовичем Шестаковым.
В Тобольске к нему примкнули геодезист Михаил Спиридонович Гвоздев, подштурман Иван Федоров и капитан Дмитрий Иванович Павлуцкий с отрядом в 400 казаков. Экспедиция прибыла в Охотский острог в 1729 г. Оттуда осенью того же года Шестаков морем перешел в Тауйскую губу и во главе крупной партии (более 100 человек, включая лишь 18 служивых) в конце ноября выступил на северо-восток.
Он двигался по южным склонам Колымского нагорья, собирая ясак с еще не попавших под «царскую руку» коряков, и по старой «традиции» брал аманатов. В пути он узнал, что незадолго до прихода русских на жителей, теперь уже подданных русского государя, напали «немирные» чукчи. Шестаков поспешил в погоню и недалеко от устья Пенжины погиб в бою 14 мая 1730 г. По неизведанным местам он прошел более 1000 км.
Участник Великой Северной экспедиции переводчик Яков Иванович Линденау в 1742 г. составил карту Северо-Востока Азии и Камчатки. На ней по материалам А. Шестакова, ясачного сборщика А. Пежемсого, работавшего по поручению Я. Линденау, и собственным данным между Охотским острогом и вершиной Пенжинской губы, т. е. на протяжении более 2000 км он нанес п-ов Тайгонос и около 30 коротких рек, впадающих в Охотское море, а также в р. Пенжину. Отчетливо показан водораздел между ними и бассейном Колымы – Колымское нагорье и горы к юго-западу, расположенные в верховьях Колымы.
Преемником А. Шестакова стал Д. Павлуцкий, совершивший в 1731—1746 гг. во главе военного отряда три похода по Чукотскому нагорью и побережью Северного Ледовитого и Тихого океанов. Первый поход (март—октябрь 1731 г.): из Нижнеколымска через верховья притоков Большого Анюя и Анадыря Д. Павлуцкий прибыл в Анадырский острог. Его отряд численностью 435 человек, включая 215 служивых, прошел оттуда на северо-восток к устью Белой, левому притоку Анадыря. По ее долине Павлуцкий поднялся к истокам (двигались очень медленно – не более 10 км в день) и, перевалив в бассейн порожистой Амгуэмы, в начале мая вышел к побережью Чукотского моря близ 178° з. д. Он планировал обойти весь Чукотский п-ов и повернул на восток вдоль берега. Вскоре он обнаружил небольшую бухту, которую пришлось обходить почему-то ночью, а затем другую, значительно крупнее, с обрывистыми берегами (Колючинская губа) – ее пересекли по льду.
Маршрут по побережью продолжался до начала июня, возможно, до окрестностей мыса Дежнева. К этому времени относится и первое столкновение с крупным отрядом чукчей, проигравших бой и понесших большие потери.
Д. Павлуцкий оставил морской берег и в течение трех недель шел на юго-запад по безлюдной и безлесной гористой местности. 30 июня неожиданно появился новый, более крупный отряд чукчей. В завязавшемся сражении, потеряв многих воинов, чукчи отступили. От пленных Д. Павлуцкий узнал о местонахождении очень большого стада оленей и захватил до 40 тыс. голов. Без «приключений» он добрался к Анадырскому заливу примерно у 175° з. д. и повернул на запад. Близ гористого мыса в середине июля на русских вновь напали чукчи и снова потерпели поражение.
Отряд Д. Павлуцкого обогнул залив Креста и по северной окраине Анадырской низменности вернулся в Анадырский острог 21 октября, выполнив первое обследование внутренних районов Чукотского п-ова (площадь около 80 тыс. км2). По возвращении капитан направил тобольскому начальству рапорт, в котором дал весьма нелестную характеристику осмотренной территории: «Чухотия [Чукотский п-ов]... пустая земля; нет ни лесов, ни других угодий, рыбных и звериных промыслов никаких, а довольно [много] каменных гор [Чукотское нагорье] и шерлобов [скал, утесов] да воды, а больше... ничего не имеется...». Очень уважительно он отозвался о своем противнике: «Чукчи народ сильный, рослый, смелый... крепкого сложения, рассудительный, справедливый, воинственный, любящий свободу и не терпящий обмана, мстительный, а во время войны, будучи в опасном положении, себя убивают».
После длительного перерыва, летом 1744 г., Д. Павлуцкий совершил второй поход по Чукотке для усмирения чукчей: из Анадырского острога во главе отряда он проследовал через вершину залива Креста на восток – к Мечигменскому заливу, а затем «вокруг» Чукотского п-ова, т. е. по побережью, к Колючинской губе. Домой вернулись старым (1731) путем. Во время походов 1731 и 1744 гг. его отряд впервые выполнил четырехкратное пересечение Чукотского нагорья.
В 1746 г. д. Павлуцкий совершил третий поход: он поднялся к истокам Анадыря, перевалил горы (Илирнейский кряж наших карт) и по одной из речек вышел к Чаунской губе. По ее восточному берегу отряд проследовал к Шелагскому мысу: оттуда удалось усмотреть остров (Айон), лежащий у входа в губу. По побережью океана Д. Павлуцкий прошел на восток на некоторое расстояние и повернул назад.
Во всех трех походах принимал участие подпрапорщик Тимофей Перевалов, выполнивший с некоторыми перерывами съемку побережья Чукотского п-ова, берегов Чукотского и Восточно-Сибирского морей на протяжении более 1500 км. Он впервые положил на карту Мечигменский залив (губа Теняха), Колючинскую губу (Анахыя), несколько небольших лагун и Чаунскую губу с о. Айон. Существует, правда, мнение, что губа Теняха – это менее крупный залив Лаврентия, расположенный чуть севернее.
На составленном Т. Переваловым чертеже отчетливо вырисовывается гористый полуостров, заканчивающийся Шелагским мысом. Он заполнил горами внутренние районы Чукотки (Чукотское нагорье) и показал р. Анадырь с несколькими левыми притоками, а также много коротких рек бассейнов Тихого и Северного Ледовитого океанов – из наиболее крупных отметим рр. Амгуэму и Паляваам.