В 1725 г. Артемий Петрович Волынский был назначен губернатором Казани. Это назначение он получил, вероятно, не без протекции цесаревны Елизаветы Петровны, которую в июле 1725 г. просил вызволить его «из здешней пеклы», то есть Астрахани. С небольшими перерывами Волынский пробыл казанским губернатором до 1731 г. Поведение его на посту губернатора оказалось не безупречным. Он был замечен в многочисленных злоупотреблениях и произволе. Но благодаря покровительству своего влиятельного дяди, Семена Андреевича Салтыкова, жалобы на губернатора остались без рассмотрения.
Переезд Артемия Петровича Волынского в Москву, а затем в Петербург, ознаменовался фантастическим взлетом его карьеры. Он сумел войти в доверие к влиятельному при дворе графу Ф. К. Левенвольде и в 1732 г. стал его помощником по конюшенной части. Эта придворная должность позволила Волынскому, с одной стороны, находиться на виду императрицы Анны Иоанновны, а с другой — сойтись с ее фаворитом Э. И. Бироном, знавшим толк в лошадях. Любовь Анны Иоанновны и Бирона к лошадям привела к тому, что в конце 1734 г. Волынский был произведен в генерал-лейтенанты. В следующем году умер Левенвольде, и Волынский занял его место, а 27 января 1736 г. в связи с днем своего рождения императрица произвела его в обер-егермейстеры.
Вскоре Волынскому представилась возможность вернуться к дипломатической деятельности. В 1735 г. возобновилась борьба России с Турцией. Россия добивалась выхода в Черное море и укрепления своих южных границ. Для разрешения этих задач с начала 1730-х гг. российская дипломатия проводила длительную и тщательную дипломатическую подготовку. В частности, Россия уступила Персии все прикаспийские провинции, захваченные в ходе Каспийского похода, в обмен на обещание совместных действий против турецкого султана. Весной 1736 г. Россия объявила войну Турции. Русские войска под командованием генерал-фельдмаршала Б. X. Миниха в ходе войны взяли Азов, Очаков, Хотин, Яссы и дважды занимали Крым.
В середине 1737 г. со стороны Турции была предпринята попытка мирного разрешения конфликта с Россией. С 16 августа по 11 ноября в украинском местечке Немирово состоялся конгресс русских, турецких и союзных России австрийских представителей. На этом конгрессе Россию представляли А. П. Волынский, П. П. Шафиров и И. И. Неплюев. Но переговоры желаемых результатов не дали. Турки под дипломатическим давлением Франции отклонили территориальные и другие требования России и покинули зал заседаний. Военные действия возобновились. 29 сентября 1739 г. в Белграде был подписан русско-турецкий мирный трактат. Россия получила Азов (без права вооружения его) и право построить крепость на донском острове Черкасе. России запрещалось держать флот на Азовском и Черном морях. Торговля через Черное море могла вестись лишь на турецких кораблях.
В марте 1738 г. русская делегация возвратилась в столицу. 3 апреля того же года «в рассуждении особливых его превосходительства заслуг» Анна Иоанновна назначила Артемия Петровича Волынского на высшую в империи должность кабинет-министра. В состав кабинета министров вошли всего два человека: Андрей Иванович Остерман и Алексей Михайлович Черкасский. О своих коллегах Волынский писал так: