Пока же Афанасий Лаврентьевич перебрался в Псков, где завел себе дом и торговое дело. Пользуясь знанием языков, он познакомился с иноземными купцами и продавал им традиционные русские товары — зерно, сало, пеньку. Но торговля, даже самая выгодная, не могла утолить его амбиций: он мечтал сделать карьеру дипломата, которая больше привлекала его, чем военная или административная служба. Помогло то, что его тесть Колобов был знаком с думным дворянином Богданом Дубровским, заместителем начальника приказа Большой казны Ф. И. Шереметева, «тайнейшего и начальнейшего боярина в царстве». Около 1640 года Ордин-Нащокин отправился в Москву, где Дубровский представил его своему начальнику и другим вельможам. Вероятно, сведущий и учтивый гость из Пскова произвел на них хорошее впечатление, поскольку уже в 1642 году его допустили к участию в межевом съезде, призванном урегулировать русско-шведские пограничные проблемы. Опыт оказался удачным: в следующем году ему было поручено самостоятельное и куда более важное дипломатическое задание.
В начале 1640-х годов после нападения казаков на турецкую крепость Азов резко обострились отношения Руси с Османской империей и вассальным ей Крымом. Воевать с ними Москва не могла — не только из-за того, что еще не восстановила силы после смуты, но и из-за боязни, что турки в случае войны заключат союз с недавним своим врагом, Речью Посполитой. Необходимо было проверить возможность такого поворота событий, собрав информацию в придунайской Молдавии — она граничила как с Польшей, так и с Турцией, в зависимости от которой находилась. Ходили слухи, что в столице княжества Яссы осуществлялись контакты между польскими и османскими дипломатами. Чтобы проверить это, туда осенью 1643 года была послана русская делегация во главе с Ординым-Нащокиным. С собой они везли подарки господарю Василию Лупу — 11 сороков и пять пар соболей и шкуру редкой чернобурой лисы. Ехать пришлось через Украину тайно, поскольку польские власти велели задерживать всех прибывающих из России.
Добравшись до Ясс, дипломаты были радушно приняты господарем, который надеялся на помощь Руси против османской деспотии. Он даже высказал просьбу о принятии Молдавии в русское подданство, хотя обе стороны понимали, что речь идет о простой дипломатической вежливости — Турция не потерпела был такого ущерба своим интересам. Однако Василий Лупу обещал оказать послу всю возможную помощь в сборе информации: «Где ни услышу де какое дурно к ево царскому величеству, или што де мне укажет его царское величество, и яз де готов ему, государю, головой своей служить». Чтобы обмануть турецких и польских шпионов при дворе, господарь объявил, что московский гость поступил к нему на службу, брал его в поездки к османской границе, помог наладить отправку донесений в Москву. В короткое время Ордин-Нащокин довольно много узнал о намерениях польского и турецкого дворов и их возможных контактах. Не укрылись от его глаз и военные приготовления на границе с Русью; обо всем этом он написал подробный отчет, позже представленный царю и его приближенным.