Посольский «поезд» уже обгоняли слухи, что царский дипломат «великими богатствы от шаха одарен», и Волынский спешил их предупредить. В письме начальнику Императорского кабинета Алексею Макарову он сообщил, что вывез из изнурительного путешествия одни долги, и шутливо жалел об отсутствии приятеля — Абрама Ганнибала, кому уже присмотрел невесту, «которая так бела, как сажа». Однако тогда Петр был весьма доволен действиями своего посланца, которому предстояло исполнять царские замыслы на Востоке.

За успешное выполнение миссии Петр I в марте 1719 года произвел молодого офицера в полковники и назначил начальником только что основанной Астраханской губернии. Это был скачок в карьере — Волынский вошел в круг принимавших важные решения лиц из числа петровского «генералитета». Но отныне его ожидала и другая мера ответственности: на высокой должности сложнее было спрятаться за чью-то спину.

Новому губернатору предстояла трудновыполнимая задача благоустройства всей юго-восточной окраины страны. На огромной территории Нижнего Поволжья (включавшей позднейшие Астраханскую, Саратовскую, Самарскую, Симбирскую губернии и Уральскую область) имелось только восемь тысяч дворов, из которых лишь 1225 принадлежали русскому населению, остальные жители были местными «ясачными инородцами», в основном татарами. На торговых площадях и караван-сараях Астрахани делали свой бизнес персы, армяне, индийцы, бухарцы, туркмены, калмыки, татары, грузины.

Расстилавшаяся от Терека до Яика (Урала) и от Астрахани до Саратова степь не имела ни дорог, ни сколько-нибудь определенных границ, ни какой-либо коронной администрации; здесь находились владения кочевых народов — калмыков во главе с влиятельным ханом Аюкой, «киргиз-кайсаков» (казахов) и каракалпаков. Все они лишь формально считались российскими подданными, и с их предводителями надо было поддерживать дружественные отношения. Сюда же вторгались крымские подданные — закубанские татары, и оседлое население должно было отбиваться от их набегов, теряя уведенных в плен родственников и соседей. На юге, на вольном Тереке, жили казаки, а их соседями были воинственные кочевники и горцы Дагестана; их «князья» и «владельцы» получали подарки и из Исфахана, и из Москвы и, таким образом, числились в «опчем холопстве», то есть одновременно признавали себя вассалами «белого царя» и иранского шаха, но на деле не были подвластны никому. Нужно было всячески «ласкать» их, чтобы не допускать набегов и прочих «пакостей» в отношении российских поселений и купцов.

Единственным надежным путем на «низ» (так называли этот край в столице) была Волга. Но она привлекала не только купцов; сюда со всей страны бежали крестьяне — от податей и крепостного права, раскольники — от официальной церкви, стрельцы, солдаты и прочие «служилые люди» — от тяжкой царской службы. В лучшем случае они основывали «вольные», никому не подчинявшиеся и не платившие налогов поселения; в худшем — становились лихими разбойниками, встречавшими торговые и казенные суда. Несмотря на усилия властей, до конца XVIII века на берегах звучали песни «понизовой вольницы»:

К тому же расположение края вдали от бдительного ока московских властей давало местным правителям возможность проявлять свой нрав и вводить свои порядки, не останавливаясь перед явными злоупотреблениями. «Здесь иное государство, а не Россия, — писал об Астрахани Волынский Шафирову на возвратном пути из Персии, — понеже, что государю и государству противно, то здесь приятно и такие дела делаются, что и слышать странно». Не случайно именно здесь в 1705 году вспыхнуло восстание против воеводских поборов и притеснений. Сам Волынский вынужден был признаться, что не имеет точных представлений о размерах губернских доходов: по «розыску» среди местных чиновников, они составляли более 200 тысяч рублей, тогда как, по сведениям губернатора, в центр доходило («по генеральной табели счисляется») только 70 тысяч.

Новоиспеченный губернатор понимал сложность поставленных перед ним задач. В июне 1719 года он обратился в Сенат с пространным докладом. Волынский просил назначить к нему нескольких «добрых комендантов и протчих управителей» и перечислил подходящих кандидатов, а также ходатайствовал о создании под его началом губернского драгунского полка, необходимого для действий на неспокойном пограничье — «от кубанцев, так от каракалпаков и от калмыков тамо не будет спокойствия, также и от своих на реке на Волге бывают великие разбои, которые б могли пресечены быть, если бы не так малолюдно тамо было». Для усиления обороны требовались артиллеристы, «искусный инженер», лекари армейского госпиталя и толковые офицеры, поскольку имевшиеся «многие негодны, от чего и солдаты весьма регулу потеряли»; для налаживания работы канцелярии губернатор нуждался в секретаре и «добрых людях» из подьячих.

Беспокоило Волынского отсутствие надежной связи и безопасных дорог: «От Саратова до Астрахани между городов по двести и по триста верст жила никакого нет; того ради как купецким людям, так и протчим проезжим и рыбным ловцам от калмыков и от кубанцев чинится великое разорение, и работных людей берут в плен; также и зимою проезд зело труден, того ради по моему б мнению надобно между городов еще сделать хотя малые городки для прибежища проезжим и для закрытия пустоты от неприятельских набегов, выбрав к поселению удобные безопасные места, дабы не так безопасно было неприятельским партиям чинить набеги» (всё это будет реализовано много лет спустя). Губернатор считал необходимым построить новую удобную пристань и таможню, чтобы воспрепятствовать провозу контрабандных товаров; его заботили нехватка судов современной постройки («новой манеры») и слабость флотской команды, ведь по замыслу Петра Астрахань должна быть современным портом и главной базой будущих военных действий на Каспийском море.

Из недатированного письма Петру можно понять, что Артемий Петрович был не в восторге от назначения. Он заявлял, что в «гражданских делах необыкновенен», жаловался на долги в две тысячи рублей «кроме прежнего» и разоренные «деревнишки малые» и даже осмелился молить, «дабы я тамо вечно не заключен был в таких моих молодых летех». Сравнение государственной службы с положением заключенного едва ли могло понравиться царю. Однако спорить с государем не приходилось. Петр же награждать слугу новыми деревнями не спешил. Но Волынский сумел о себе напомнить — осенью 1719 года попросил Макарова представить царю «древнего дворянина» Василия Яковлева, который сражался за отца и старшего брата государя под Конотопом и Чигирином и был еще настолько бодр, чтобы желать воеводства в Пензе. Артемий Петрович предупреждал, что «сей старичок зело честолюбив и спесив, так же и лжец жестокий», но был уверен, что ветеран «его царскому величеству забавен будет».

Присмотрел он и выгодную «партию» в лице двоюродной сестры царя по материнской линии молодой Александры Львовны Нарышкиной. В сентябре—октябре 1719 года Волынский в нескольких письмах из Москвы извещал Макарова об объяснении с девушкой при посредстве ее тетки Ульяны: избранница передала ему, что на предложение руки и сердца «склонна, но без повеления его царского величества и всемилостивой царицы не смеет обязаться со мною словом». Но расторопный жених сам нашел дорогу к царице, и она написала юной Нарышкиной о согласии. Тут, правда, на заочное сватовство надулась тетка — и дело-то решено «мимо нее», и «штиль не тот в письме». Вслед за тем и невеста пришла «в сумнение», достойно ли, что брак разрешен «не словом, а письмом»; в итоге Екатерина оставила дело на ее «рассуждение», о чем и сообщила Волынскому.