Родился в семье слесаря. По настоянию отца окончил Московский авиационный институт и поступил на работу на опытный завод КБ Яковлева. В 1944 поступил в Высшую дипломатическую школу, в 1946 с отличием закончил её, защитив диссертацию, был принят на службу в Министерство иностранных дел в учебный отдел. Довольно длительное время Добрынин проработал в Секретариате министерства под началом Молотова, Шепилова, Громыко, Зорина. В 1957 назначен заместителем Генерального секретаря ООН. В 1959 вернулся в Москву, возглавив Департамент Северной Америки в МИД.
В 1962 направлен в Вашингтон в качестве посла СССР в США. На этом посту сыграл важнейшую роль в разрешении Карибского кризиса, в разрядке международной напряженности и стабилизации советско-американских отношений. Проработал советским послом в Соединенных Штатах почти 25 лет; за это время в СССР сменились 5 Генсеков, а в США — 6 президентов.
В 1986 избирается Секретарем ЦК и возвращается в Москву. До 1988 он является заведующим Международным отделом ЦК КПСС. С 1988 — советник Председателя Президиума Верховного Совета СССР, а с 1990 — Президента СССР. В 1992 вернулся в МИД в качестве советника-консультанта, имея пожизненный ранг Чрезвычайного и Полномочного посла.
Скончался 6 апреля 2010 года в Москве .
Урна с прахом А. Ф. Добрынина — на Ваганьковском кладбище, в Москве, в могиле родителей.
Анатолий Добрынин был назначен послом в США на очередном заседании Политбюро 4 января 1962. Его кандидатуру выставил Никита Хрущёв взамен уходившего на пенсию М. А. Меньшикова. На тот момент ключевой проблемой в отношениях с Западом был Германский вопрос и, в особенности, статус Берлина. Хрущёв и Громыко потребовали от Добрынина уделить максимальное внимание этой проблеме. 15 марта Анатолий Добрынин вступил в должность.
Первым же серьёзным испытанием советско-американских отношений при Добрынине стал кризис отнюдь не в Германии, а на Кубе. Советское руководство приняло решение разместить там ракеты средней дальности с целью предотвратить возможные повторные попытки США вторгнуться на остров. Американцы обнаружили монтаж ракет 14 октября. Разразился Карибский кризис.
18 октября в Вашингтон прибыл министр иностранных дел СССР Андрей Громыко. Вместе с Добрыниным он провел встречу с президентом США Джоном Кеннеди. В этой беседе Громыко ясно дал понять, что на Кубе нет советского наступательного оружия, но сразу после того, как он сел в самолет и улетел в Москву, Кеннеди выступил с обращением к нации, где рассказал о развертываемых Советским Союзом ракетах.
В разрешении кризиса Добрынин сыграл важнейшую роль. В ночь с 27 на 28 октября он провел тайную встречу с братом президента США Робертом Кеннеди, и в ходе этой беседы было решено демонтировать советские ракеты на Кубе в обмен на демонтаж американских ракет в Турции.
После Кеннеди и Джонсона президентом США стал Ричард Никсон. Добрынин проводил частые встречи с Никсоном и его советником по делам национальной безопасности Генри Киссинджером. Между посольством СССР и Белым домом была проведена прямая закрытая телефонная линия.
В октябре 1969 Добрынину было поручено передать в администрацию США предложение Советского Союза о начале переговоров об ограничении гонки вооружений. С ноября 1969 по май 1972 велись активные переговоры по закрытой линии, и 26 мая в ходе визита Никсона в Москву был подписан советско-американский Договор об ограничении систем противоракетной обороны, в 1979 — об ограничении стратегических вооружений.
В ноябре 1985 в Женеве прошла встреча Рональда Рейгана и Михаила Горбачева, в которой началась новая эпоха советско-американских отношений. Стало очевидно, что Холодная война подходила к концу.
Весной 1986 Добрынин был избран Секретарем ЦК по международным вопросам и покинул Вашингтон, чтобы занять эту должность. Так завершилось рекордное в истории отечественной дипломатии 25-летнее пребывание Добрынина на посту посла в США.
С 1986 по 1988 год руководил Международным отделом ЦК КПСС.
Добрынин — автор многочисленных публикаций в отечественной и зарубежной прессе. В частности, он является автором автобиографической книги «Сугубо доверительно» (ISBN 5-85212-078-2), переведенной на многие языки и являющейся по сути дидактическим пособием «добрынинской школы» дипломатии.
Анатолий Фёдорович — Герой Социалистического Труда, Заслуженный работник дипломатической службы Российской Федерации, Почётный доктор Дипломатической академии МИД России.
18 августа 2009 года награждён орденом Почёта за большой вклад в реализацию внешнеполитического курса Российской Федерации и многолетнюю дипломатическую службу.
Закончившаяся холодная война не привела к устранению всех разногласий между США и Россией — преемницей СССР, особенно по вопросу о том, каким должен быть многополярный мир после этого соперничества.