Александр Алексеевич Авдеев родился 8 сентября 1946 года в Кременчуге. В 1968 году окончил МГИМО, после чего отправился в Алжир референтом-секретарем генерального консульства СССР в городе Аннабе. C 1971 года Авдеев работал в посольстве СССР в Алжире в ранге атташе. В 1977-1985 годах в ранге второго и первого секретаря Авдеев работал в посольстве СССР во Франции, а в 2002-2008 годах был послом РФ во Франции. До этого в 1987-1990 годах был послом СССР в Люксембурге, в 1992-1996 — послом РФ в Болгарии, в 2007-2008 — по совместительству послом в Монако. В 80-е — 90-е годы работал в МИД СССР и РФ. Награжден орденом "За заслуги перед Отечеством" IV степени, орденами Почета и Дружбы.
12 мая 2008 года Александр Авдеев был назначен на должность министра культуры РФ.