Родился 25 июля 1959 г. в Киеве Украинской ССР (ныне – Украина) в семье главного инженера института "Промстройпроект".
В 1980 г. окончил Киевский государственный институт театрального искусства (ныне - Киевский национальный университет театра, кино и телевидения) им. И. К. Карпенко-Карского.
На последнем курсе вуза был принят на Киностудию им. А. Довженко (Киев). В 1980 г. дебютировал в фильме "Овод" Николая Мащенко по мотивам романа Этель Лилиан Войнич, где сыграл главную роль - итальянского революционера Артура Бертона. В 1981 г. за этот фильм получил приз "Золотая нимфа" за лучшую мужскую роль на Международном телевизионном фестивале в Монте-Карло, в 1982 г. был удостоен государственной премии УССР им. Тараса Шевченко.
Среди других известных киноролей начала 1980-х гг.: Игорь Астрахов в остросюжетном фильме "На гранатовых островах" (1981, режиссер Тамара Лисициан), Хоакин в рок-опере "Звезда и смерть Хоакина Мурьеты (1982, Владимир Грамматиков), Ланселот Фортескью в детективе "Тайна "Черных дроздов" (1983, Вадим Дербенев), Гриффин в фантастической ленте "Человек-невидимка" (1984, Александр Захаров).
В 1984-1990 гг. Андрей Харитонов служил актером Малого театра в Москве. Был задействован в спектаклях "Накануне" по роману Ивана Тургенева, "Доходное место" по комедии Александра Островского, "Двое на качелях" по пьесе Уильяма Гибсона и др.
В 1991 г. в первый и единственный раз выступил в качестве режиссера, сняв художественный фильм "Жажда страсти" по мотивам рассказов Валерия Брюсова (главную роль в нем сыграла Анастасия Вертинская). Картина получила специальную премию "Фильм для избранных" на сочинском фестивале "Кинотавр".
Во второй половине 1990-х гг. работал режиссером-постановщиком программ "Фабрика грез" и "Фильмы нашей памяти" на телеканале ОРТ. В 2007 г. вел программу "Внедрение" на телеканале "Звезда".
В 1990-2000-х гг. продолжал играть в кино, в том числе в сериале "Юнкера" (2007), фильме "Подпоручик Ромашовъ" (2012, реж. Игорь Черницкий , приз за лучшую роль второго плана кинофестиваля "Золотой витязь"). Всего за карьеру снялся более чем в 40 фильмах и сериалах. Последняя роль - начальник горотдела образования в криминальной драме "Под прицелом" (2013, реж. Виктор Конисевич).
Выступал в антрепризах. В 2017 г. был занят в пьесе Питера Моргана "Аудиенция" в Театре наций.
Был женат на Ольге Смирягиной.