Футбольну кар'єру розпочав у «Ворсклі». У футболці полтавського клубу дебютував 1 серпня 1993 року в переможному (2:1) виїзному поєдинку 1/64 фіналу кубку України проти новомосковського «Металурга». Андрій вийшов на поле на 82-й хвилині замість Юрія Левчука[1]. У Першій лізі України дебютував 15 серпня 1993 року в нічийному (0:0) домашньому поєдинку 1-го туру проти олександрійської «Поліграфтехніки». Захаров вийшов на поле на 32-й хвилині замість Вазгена Манасяна, а на 64-й хвилині отримав жовту картку[2]. Першим голом за «Ворсклу» відзначився 24 вересня 1993 року на 67-й хвилині нічийного (1:1) домашнього поєдинку 9-го туру Першої ліги України проти стрийської «Скали». Андрій вийшов на поле на 67-й хвилині замість Олександра Оголюка[3]. У полтавському клубі провів сезон 1993/94 років, за цей час у Першій лізі України зіграв 24 матчі (2 голи), ще 4 поєдинки провів у кубку України.
Напередодні старту сезону 1994/95 років перебрався у «Водник». У футболці херсонського клубу дебютував 19 вересня 1994 року в програному (1:2) домашньому поєдинку 9-го туру Другої ліги України проти маріупольського «Азовця». Захаров вийшов на поле в стартовому складі, а на 68-й хвилині його замінив Євген Калюжний[4]. Восени 1994 року провів 4 поєдинки[5].
У 1995 році перейшов до «Десни»[6]. У футболці чернігівського клубу дебютував 22 вересня 1995 року в нічийному (1:1) домашньому поєдинку 13-го туру групи «А» Другої ліги України проти калуського «Хіміка». Андрій вийшов на поле на 84-й хвилині замість Володимира Дробота[7]. Восени 1995 року провів 2 поєдинки за «Десну».
