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