Родился 2 сентября 1979 г. в Калининграде.
В 2000 г. Андрей Клычков окончил Калининградский юридический институт МВД РФ (ныне филиал Санкт-Петербургского университета МВД) по специальности "юриспруденция", в 2004 г. - Российский университет инноваций (Москва) по специальности "политтехнология", в 2008 г. - очно-заочное отделение Дипломатической академии МИД РФ по специальности "международные отношения".
После окончания юридического института работал в милиции Калининграда в уголовном розыске.
В июле 2001 г. вступил в Коммунистическую партию Российской Федерации (КПРФ). Работал с обращениями граждан в общественной приемной КПРФ. Был помощником юрисконсульта, затем - заместителем руководителя юридической службы центрального комитета (ЦК) КПРФ. Представлял интересы партии в Центральной избирательной комиссии России, Верховном суде и т. д.
Был помощником депутата Государственной думы РФ (Анатолий Локоть, член фракции КПРФ).
12 марта 2006 г. Андрей Клычков участвовал в выборах депутатов Калининградской областной думы IV созыва от КПРФ (входил в состав Советской региональной группы), однако в областной парламент не прошел.
Занимал должности референта, старшего референта аппарата фракции КПРФ в Госдуме РФ.
2 декабря 2007 г. баллотировался в Госдуму V созыва от КПРФ (под №2 в региональной группе №52, Нижегородская область). В парламент не прошел.
В 2007-2009 гг. - член ЦИК РФ с правом совещательного голоса.
В октябре 2008 г. на XIII съезде КПРФ был избран членом центрального комитета партии, затем неоднократно переизбирался.
В 2009-2017 гг. - депутат Московской городской думы V-VI созывов.
11 октября 2009 г. был избран в Московскую городскую думу V созыва по списку КПРФ (входил в общегородскую часть списка, возглавлял региональную группу №14). В городском парламенте стал руководителем фракции КПРФ.
14 сентября 2014 г. вновь был избран депутатом Мосгордумы VI созыва от КПРФ по избирательному округу №21 (часть района Выхино-Жулебино и Рязанского района Москвы). Получил 37,32% голосов, опередив кандидата от "Единой России" Владимира Зотова (32,16%). В новом составе парламента переизбран главой фракции коммунистов.
В Мосгордуме был заместителем председателя комиссии по делам общественных объединений и религиозных организаций. Входил в состав комиссий по градостроительству, государственной собственности и землепользованию, по законодательству, регламенту, правилам и процедурам. Был членом объединенной комиссии Московской городской думы и Московской областной думы по координации законотворческой деятельности по городскому хозяйству и жилищной политике.
Являлся советником председателя ЦК КПРФ Геннадия Зюганова.
Был секретарем московского городского комитета КПРФ.
В декабре 2011 г. и сентябре 2016 г. баллотировался в Государственную думу РФ VI и VII созывов по списку КПРФ от Москвы, однако думский мандат не получил.
С 2017 г. руководит Орловской областью.
5 октября 2017 г. указом главы государства Андрей Клычков был назначен временно исполняющим обязанности губернатора Орловской области. Сменил на этом посту Вадима Потомского, ставшего заместителем полпреда президента РФ в Центральном федеральном округе.
9 сентября 2018 г. избран губернатором Орловской области, получив 83,55% голосов избирателей (баллотировался от КПРФ). Второе место занял депутат регионального парламента Руслан Перелыгин от "Справедливой России" (4,84%). Инаугурация Андрея Клычкова состоялась 14 сентября того же года.
В 2021 г. участвовал в выборах в Госдуму РФ VIII созыва по списку партии КПРФ (№4 общефедеральной части списка кандидатов). После выборов отказался от депутатского мандата.
10 сентября 2023 г. вновь победил на выборах губернатора Орловской области, набрав 82,09% голосов избирателей (был выдвинут КПРФ). Его ближайший соперник, координатор областного отделения ЛДПР и руководитель партийной фракции, вице-спикер Орловского облсовета Владислав Числов (от ЛДПР), получил 8,37%. 15 сентября того же года Андрей Клычков вступил в должность. Согласно уставу Орловской области является председателем правительства региона.
Член президиума центрального комитета КПРФ, секретарь ЦК КПРФ.