Наверное, Артемий Петрович с радостью вырвался из столицы. В 1736 году началась Русско-турецкая война. Был взят Азов. Пройдя безводные степи, войска под командованием фельдмаршала Миниха впервые вторглись в Крым. Армия без боя заняла ханскую столицу Бахчисарай, но вынуждена были повернуть обратно. Татарская конница угоняла лошадей и скот во время стоянок, нападала на фуражиров и обозы. Не хватало провианта, а непривычная еда и плохая вода вызывали массовые заболевания. Оборотной стороной славы вторжения в недосягаемые прежде владения хана стали огромные потери: от болезней погибло 30 тысяч солдат и офицеров — более половины личного состава, тогда как на поле боя пали всего две тысячи человек. Опасаясь совместных русско-австрийских действий, турки весной 1737 года согласились на переговоры. Императрица отправила на конгресс в пограничный польский город Немиров делегацию во главе со старым знакомым Артемия Петровича Петром Шафировым; вторым послом был назначен сам Волынский; третьим — Иван Неплюев, долгое время бывший резидентом в Стамбуле. Военные действия при этом не прерывались — армия Миниха готовилась брать турецкую крепость Очаков рядом с устьем Днепра, а армия фельдмаршала Ласси вновь двинулась в Крым.
Обер-егермейстер получил на дорогу годовое жалованье и отбыл в Москву, где в кругу семьи задержался, так что в начале мая получил выговор за промедление. Там он должным образом экипировался. По старому московскому обычаю Анна Иоанновна решила приодеть посла и распорядилась «…из конфискованных пожитков вещи отпустить ему за поставленные цены без переторжки». «И по тому ее императорского величества указу, отобранное им, господином Волынским… по цене на 680 рублев на 61 копейку, ему отпущено, и те деньги у него приняты. Да сверх того отдано ему же, господину Волынскому из конфискованных же пожитков кафтан дикой атласной, шит китайским образцом; доха камчатая, шита на бельем меху; доха же шита шелком на бельем же меху; шапка низана бисером; рукавицы якуцкие, шиты по китайски, по цене на 10 рублев» {264}. (По возвращении с конгресса дипломат исправно сдал полученные напрокат кафтан, доху и другие вещи в Канцелярию конфискации {265}.) Кроме того, государыня выдала Волынскому «в награждение тысячу рублев, которые деньги и имеете вы, прибыв в Москву, взять по сему нашему указу из Конюшенной канцелярии из наличных денег, остаточных за годовыми расходами». 17 июня он на целом поезде из шестидесяти подвод (в первоначально намеченных пятидесяти телегах весь багаж не поместился) отправился на юг — в края, где прошла его боевая молодость. 11 июля послы прибыли в заштатный городишко, где негде было даже разместиться их свите — в итоге разбили шатры в дубовой роще. Дипломаты рассчитывали на «добрые диспозиции»: союзники-австрийцы наконец вступили в войну на Балканах, а Миних 2 июля стремительным штурмом взял Очаков.
Врученная послам инструкция предусматривала заключение мира на наивыгодных условиях — передачу России Крыма и всего северного побережья Черного моря от Кубани до Днестра; впрочем, Остерман допускал сохранение Крыма под властью султана, но с оговоркой, чтобы он убрал оттуда беспокойных татар и поселил на их место «другого закону подданных турецких». В случае же дальнейшего «преуспевания наших военных действ» надлежало требовать у турок провести границу по Дунаю, а Валахию и Молдавию объявить независимыми «удельными особливыми княжествами» под протекторатом России.
Артемий Волынский, вероятно, в этот момент гордился: спустя 25 лет после неудачного Прутского похода он — теперь уже не молодой офицер, а полномочный посол — должен был не просить, а диктовать туркам мир. Но вскоре прибывавшие в посольские шатры донесения с театра военных действий радовать перестали. Австрийские войска после первых успехов в Сербии и Валахии начали терпеть поражения и оставили занятый ими Бухарест. Миниху же пришлось срочно уводить из Очакова победоносную армию — она таяла из-за болезней, и фельдмаршал писал Бирону, что его солдаты «умирают, как мухи». Армия Ласси после безрезультатного похода в Крым также страдала от голода и болезней. Молдавия и Валахия стали причиной раздора среди союзников — австрийцы подали письменный протест против русских предложений и в ультимативной форме сообщили туркам свои претензии на Боснию и большую часть Валахии.