Другая страна, близкая по историческим связям к России, традициям совместной борьбы с фашистской Германией. Работа здесь предстояла, пожалуй, не менее трудная и сложная. Прошло всего несколько лет после подписания в июне 1955 г. советско-югославской декларации, положившей начало нормализации отношений между двумя государствами. Во всем сказывалось наследие недавнего прошлого, когда такие отношения практически были свернуты. Чтобы положения декларации наполнялись конкретным содержанием, требовались дела.
Уже при первой встрече с президентом ФНРЮ И. Броз Тито новый посол почувствовал, каких усилий будет стоить каждый шаг в дальнейшем улучшении отношений между прежде дружественными странами. Руководитель югославского государства откровенно высказывался на этот счет, хотя и держался просто, как со старым знакомым. С И. Броз Тито Алексей Алексеевич до этого встречался на приеме в посольстве дружественного государства. Н. С. Хрущев тогда подвел А. А. Епишева к столу, где стоял И. Броз Тито, и в привычной для себя свободной манере сказал: «Вот еще генерал, хотя и не в военной форме».
Собеседники быстро нашли общий язык, разговорились. Президент поинтересовался, где Алексей Алексеевич воевал, в каких боях участвовал, где работает сейчас.
Что ж, может быть, та встреча сказалась и на новом назначении А. А. Епишева? Во всяком случае, как выяснилось, руководитель югославских коммунистов его не забыл, что немало значило в работе.
В Белграде сразу же довелось включиться в реализацию мер, принимаемых правительствами СССР и ФНРЮ для введения нормального договорного положения. А. А. Епишев участвует в заключении ряда соглашений, способствующих развитию советско-югославского сотрудничества. В марте 1961 г. подписывается план культурного и научного сотрудничества, затем соглашение о взаимных поставках товаров на 1961—1965 гг.
Ветеран советской дипломатии В. Ф. Грубьяков охотно откликнулся на нашу просьбу вспомнить то время, когда А. А. Епишев работал в Белграде. Василий Федорович тогда был помощником министра иностранных дел СССР, участвовал в советско-югославских переговорах, был хорошо знаком с Алексеем Алексеевичем.
— Нелегко приходилось тогда послу в Югославии, — вспоминает Василий Федорович. — Всегда бросалось в глаза его умение находить верный тон в разговорах с югославскими товарищами, добиваться, чтобы прошлое не затмевало перспективу.
В посольстве анализируется ход выполнения протокола о товарообороте между двумя странами. В одной из информаций А. А. Епишев отмечает, что советские внешнеторговые организации не удовлетворяют запросы югославской страны в олове, коксе, каучуке. Высказываются возможные последствия таких действий.
С улучшением отношений между государствами создавались условия для более широкого знакомства со страной. Многое дает послу поездка в Македонию. Расширяются наши культурные связи с этой республикой. Широкую популярность завоевывает выставка советской книги в Скопле, открывшаяся в ноябре 1961 г.
Развитию сотрудничества между двумя странами служит расширение знакомств посла с югославскими руководителями, установление с ними доверительных отношений. Алексей Алексеевич стал приглашать к себе югославских товарищей, как он потом рассказывал, на сибирские пельмени. Татьяна Алексеевна слыла хорошей мастерицей этого блюда. По ее словам, у них бывали в гостях Ранкович, Кардель, другие ответственные работники. За столом, понятно, разговор не сводился к гастрономическим качествам сибирских пельменей. В дружественной обстановке более отчетливо выяснялись точки зрения собеседников, таяли остатки недоверия, подозрительности, которые в свое время затронули отдельных югославских работников. Тем самым облегчалась дальнейшая нормализация отношений между двумя государствами.
Всего около полутора лет довелось А. А. Епишеву поработать в Югославии. Сделал он немало для улучшения отношений с этой социалистической страной, оставил там добрый след. Не случайно, уже будучи начальником ГлавПУ, он не раз совершал поездки в Югославию, встречался не только с военными работниками, но и с государственными деятелями.
В октябре 1964 г. А. А. Епишев направляется в Белград в связи с трагической гибелью во время авиационной катастрофы советской военной делегации во главе с Маршалом Советского Союза С. С. Бирюзовым. Вместе с тем Алексей Алексеевич имел поручение ЦК КПСС встретиться с Генеральным секретарем ЦК СКЮ, президентом СФРЮ И. Броз Тито. Ему вменялось в обязанность проинформировать югославского руководителя о решениях октябрьского (1964 г.) Пленума ЦК КПСС, освободившего Н. С. Хрущева от занимаемых должностей. Беседа длилась долго. У И. Броз Тито возникло немало вопросов, которые касались и дальнейших перспектив развития советско-югославских отношений и возможных перемен во внешней политике СССР. На все вопросы он получил исчерпывающие ответы.