Семейное предание утверждало, что в XIV веке его предок, дукс (то есть герцог) Величко, прибыл из Италии на службу к тверскому князю Александру Михайловичу, получив на новой родине имя Дмитрий и прозвище Красный, то есть «красивый». Сын его, тоже Дмитрий, участвовал в восстании тверичей против ханского баскака Шевкала, по щеке его прошлась татарская сабля, и его потомков прозвали Нащокины. Правнук Дмитрия, убитый в сражении при Орше в 1514 году, получил другое прозвище, Орда — вероятно, он побывал в Золотой Орде в плену или в составе русского посольства. От него пошла особая ветвь рода Нащокиных — Ордины-Нащокины. Обе ветви обосновались на северо-западе Руси, где были помещиками вплоть до XIX века — один из них, Павел Нащокин, был близким другом еще одного местного помещика, Александра Пушкина.

На Руси в правящей элите давала о себе знать тенденция выводить свои корни от иноземных предков. Поэтому историю о дуксе Величко вряд ли стоит принимать всерьез. Как и другое предание о том, что фамилия Нащокин происходит от рода курляндских баронов фон Сакен. В чем можно не сомневаться, так это в том, что к началу XVII века и от власти, и от богатства Ордины-Нащокины были далеки. Один из них, правда, при царе Федоре Ивановиче был наместником крепости Белгород, вскоре разрушенной татарами. Его племянник Лаврентий Денисович служил в городке Опочка недалеко от Пскова, защищал русские рубежи от врагов. В его семье около 1606 года (точная дата неизвестна) и родился сын Афанасий, которому довелось прославить имя Ординых-Нащокиных в истории.

Мы ничего не знаем о том, как жило их семейство в годы Смуты, когда Псковщина подвергалась набегам то поляков, то шведов, то своих самозванцев. Известно, что юный Афанасий был любознателен и прилежен в учебе. Он не только обучился у местного священника русской грамоте и счету, но и узнал от заезжего поляка основы польского и латинского языков. В отличие от остальной Руси в приграничном Пскове знание иностранных языков было делом обычным. Необычной была тяга дворянского отрока к чтению, сохранившаяся на всю жизнь. Детей с такими наклонностями нередко отдавали в монахи, но Афанасия ждала иная судьба. В 15 лет отец отвез его в Псков и записал на государеву службу как «сына боярского» — это было не сословное обозначение, а название незначительной служилой должности. После этого юноша вернулся в родную Опочку, где нес службу до начала 1630-х годов. Тогда, приехав по делам в Псков, он подружился с местным дворянином Василием Колобовым и сосватал за себя его дочь Пелагею. Как и большинство русских женщин того времени, Пелагея Васильевна бледной тенью прошла по страницам истории; супруг не упоминал ее имени в документах, не писал ей нежных писем, да и читать она, вероятно, не умела. Из их детей известен только сын Воин. Это редкое имя отсутствует в святцах: возможно, оно отражало патриотизм Афанасия, его желание, чтобы сын стал защитником Отечества. Есть и другая вероятность: имя было дано в честь кого-то из предков, как позже одному из потомков родственного семейства Нащокиных Воину Васильевичу, отцу того самого пушкинского друга. Как бы то ни было, в будущем Воин оказал заметное и совсем не благотворное влияние как на карьеру отца, так и на всю его жизнь.

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

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

Добравшись до Ясс, дипломаты были радушно приняты господарем, который надеялся на помощь Руси против османской деспотии. Он даже высказал просьбу о принятии Молдавии в русское подданство, хотя обе стороны понимали, что речь идет о простой дипломатической вежливости — Турция не потерпела был такого ущерба своим интересам. Однако Василий Лупу обещал оказать послу всю возможную помощь в сборе информации: «Где ни услышу де какое дурно к ево царскому величеству, или што де мне укажет его царское величество, и яз де готов ему, государю, головой своей служить». Чтобы обмануть турецких и польских шпионов при дворе, господарь объявил, что московский гость поступил к нему на службу, брал его в поездки к османской границе, помог наладить отправку донесений в Москву. В короткое время Ордин-Нащокин довольно много узнал о намерениях польского и турецкого дворов и их возможных контактах. Не укрылись от его глаз и военные приготовления на границе с Русью; обо всем этом он написал подробный отчет, позже представленный царю и его приближенным.

В своих донесениях он рекомендовал наладить с дружественной православной Молдавией более тесные отношения — например, присылать туда на продажу украшения из золота и серебра. Не упустил случая и покритиковать организацию посольской службы и недостатки русской политики в целом: «Житье наше русское, что царя-колокола звон —