Александр Алексеевич Авдеев родился 8 сентября 1946 года в городе Кременчуг Полтавской области Украинской ССР.
В 1968 году окончил Московский государственный институт международных отношений МИД СССР.
В 1968 1973 годах – секретарь генконсульства СССР в Аннабе, атташе посольства СССР в Алжире.
В 1973 1977 годах – в центральном аппарате МИД СССР.
С 1977 по 1985 год – второй, первый секретарь посольства СССР во Франции.
С 1985 по 1987 год – советник, заведующий сектором 1 го Европейского отдела МИД СССР.
В 1987 1990 годах – Чрезвычайный и Полномочный посол СССР в Люксембурге.
В 1990 1991 годах – первый заместитель начальника Первого Европейского управления МИД СССР.
В 1991 1992 гг. – заместитель министра внешних сношений СССР.
В 1992 году – руководитель Департамента стран СНГ МИД РФ.
В 1992 1996 годах – посол СССР в Республике Болгария.
В 1996 1998 гг. – заместитель министра иностранных дел РФ.
С 30 октября 1998 по 23 февраля 2002 года – первый заместитель министра иностранных дел РФ. Принимал участие в международных конференциях и мероприятиях по линии ОБСЕ (Венская встреча и другие).
С марта 2002 года – по 2008 год - Чрезвычайный и Полномочный Посол РФ во Французской Республике.
В 2008 году – Министр культуры Российской Федерации.
Имеет дипломатический ранг Чрезвычайного и Полномочного Посла.
Владеет французским, итальянским, английским и болгарским языками.
Награжден орденом "За заслуги перед Отечеством" IV степени (Указ Президента РФ, ноябрь 1999 года) за большой личный вклад в политическое урегулирование кризиса вокруг Косова и активное участие в проведении линии РФ на Балканах.
Лауреат премии "Лучшие перья России" (1999). Премия вручалась впервые в декабре 1999 года, ее учредители – Союз литераторов, Союз работников телевидения и другие организации.
Женат, есть сын.