Ордин-Нащокин родился предположительно в 1605 году в семье дворянина в пригороде Пскова Опочке. Любознательность и тяга к учению были характерны для него с ранних лет; тогда же зародилась любовь к чтению. Местный священник учил его грамоте, служилый поляк – латинскому и польскому языкам. Когда Афанасию исполнилось 15 лет, отец отвез его в Псков и записал в полк на государеву службу. Образованный, начитанный, владевший несколькими языками, обходительный Ордин-Нащокин сделал карьеру благодаря собственному таланту и трудолюбию.
В начале 1640-х годов семья Ординых-Нащокиных переехала в Москву. Молодой дворянин был принят в доме влиятельного боярина Ф.И. Шереметева.
К этому времени обострились русско-турецкие, а значит, и русско-крымские отношения. Москве важно было знать, существуют ли польско-турецкие договоренности о совместных действиях против России. Выполнить эту задачу было поручено Ордину-Нащокину.
24 октября 1642 года он выехал из Москвы с тремя помощниками в столицу Молдавии Яссы. Молдавский господарь Василе Лупу радушно принял посланца русского царя, благодарил за подарки и обещал всяческую помощь.
Ордин-Нащокин собирал информацию о намерениях польского и турецкого правительств и их военных приготовлениях, а также следил за событиями на границе. От его внимания не ускользали действия польских резидентов в Бахчисарае и Стамбуле. Через доверенных лиц Ордин-Нащокин знал, например, о чем шел разговор на польском сейме в июне 1642 года, о противоречиях внутри польско-литовского правительства по вопросу об отношениях с Россией. Неустанное наблюдение вел он и за действиями крымских ханов и сообщал в Москву, что послов их, ехавших от царя, перебили литовцы, что сами они готовят свои армии для нападения на Россию. Миссия Ордина-Нащокина имела существенное значение и для большего сближения Молдавии с Россией. По итогам наблюдений Ордина-Нащокина и по его предложению весной 1643 года в Стамбул было направлено посольство во главе с И.Д. Милославским, что позволило заключить мирный договор между Россией и Турцией. Соглашение снимало угрозу с южного направления, предотвращая военные акции крымцев против России.
В 1644 году Ордину-Нащокину поручили изучить обстановку на западных границах и настроения в Речи Посполитой, в частности проверить слухи о якобы готовящемся польско-датском вторжении в Россию. Он выяснил, что внутренние смуты в Польше и Литве не позволят Владиславу IV заняться сведением пограничных счетов с Россией. Да и Дания, ведшая борьбу со Швецией, по данным дипломата, не намерена была ссориться с Россией.
После смерти Михаила Федоровича в 1645 году престол занял его сын Алексей. К власти пришел Б.И. Морозов, свояк царя, сменивший Ф.И. Шереметева, покровительствовавшего Ордину-Нащокину. Последний, оставшись не у дел, уехал в свое псковское имение. Там его и застал мятеж 1650 года, причиной которого была спекуляция хлебом. Афанасий Лаврентьевич предложил правительству план подавления бунта, что впоследствии позволило ему вернуться на службу.
В середине 1650-х годов Ордин-Нащокин стал воеводой Друи, небольшого городка Полоцкого воеводства, непосредственно примыкавшего к шведским владениям в Прибалтике. Переговоры воеводы с неприятелем закончились выводом шведских войск из района Друи. Он вел переговоры и с жителями Риги о переходе в русское подданство. Организовал разведку, намечал пути продвижения русских войск, жителей Литвы убеждал в необходимости совместной борьбы со шведами. Летом 1656 года в Митаве Ордин-Нащокин добился согласия герцога Иакова помогать России, а 9 сентября Россия подписала договор о дружбе и союзе с Курляндией.
Отметив успехи Ордина-Нащокина, царь Алексей Михайлович назначил его воеводой Кокнесе, подчинив ему всю завоеванную часть Лифляндии. В ведение воеводы были переданы все занятые русскими войсками города Прибалтики. Ордин-Нащокин стремился утвердить среди латышей добрые отношения к России. Он возвращал населению несправедливо изъятое имущество, сохранял городское самоуправление по образцу магдебургского права, всячески поддерживая горожан, в основном торговцев и ремесленников.