Родился 13 августа 1960 г. в селе Хоронь Хасанского района Приморского края в семье военнослужащего.
В 1982 г. окончил факультет вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова.
В 1982–1999 гг. служил в органах государственной безопасности СССР и РФ. По данным СМИ, работал в структурах 3-го управления (военная контрразведка) КГБ СССР, затем был переведен в центральный аппарат Комитета. С середины 1990-х гг. был сотрудником департамента анализа, прогноза и стратегического планирования ФСБ РФ (в августе 1998 г. департамент возглавил Сергей Иванов).
В 1999-2001 гг. - заместитель руководителя аппарата Совета безопасности РФ. Аппарат в этот период возглавляли Владимир Путин (март - август 1999 г.), Сергей Иванов (1999-2001).
С марта 2001 г. - помощник министра обороны РФ, с октября 2004 г. по апрель 2008 г. - начальник аппарата министра обороны Сергея Иванова. После его ухода с поста главы ведомства в феврале 2008 г. Андрей Чоботов в течение двух месяцев оставался в своей должности при новом министре Анатолии Сердюкове. В Минобороны Чоботов курировал работу управления делами, управлений информации и общественных связей, международного военного сотрудничества и приемной ведомства.
1 ноября 2004 г. был уволен с военной службы в запас.
С 12 июня 2008 г. по 30 декабря 2011 г. - член Военно-промышленной комиссии при правительстве РФ, которую возглавлял вице-премьер правительства Сергей Иванов (в 2014 г. преобразована в Военно-промышленную комиссию РФ под председательством президента РФ).
В 2012-2016 гг. возглавлял секретариат руководителя Администрации президента РФ Сергея Иванова, с августа 2016 г. – Антона Вайно.
С 27 сентября 2017 г. по 23 мая 2023 г. - начальник Управления президента РФ по вопросам противодействия коррупции (входит в структуру Администрации президента РФ). Сменил на этом посту Олега Плохого.
Ответственный секретарь Совета при президенте по противодействию коррупции (2017-2023).
Генерал-лейтенант запаса (2002).
Действительный государственный советник РФ I класса (2010).
Отмечен почетной грамотой правительства РФ (2010).