Родился 1 февраля 1971 г. в г. Череповце Вологодской области.
В 1998 г. окончил Череповецкий государственный университет по специальности "электропривод и автоматика промышленных установок и технологических комплексов". В 2014 г. в Российской академии народного хозяйства и государственной службы при президенте РФ (РАНХиГС) прошел профессиональную переподготовку по программе подготовки высшего уровня резерва управленческих кадров, в 2017-2018 гг. - по программе кадрового управленческого резерва президента РФ "Государственное и муниципальное управление". Имеет степень магистра делового администрирования (MBA), полученную в Высшей школе экономики.
В 1990 г. окончил Череповецкий металлургический техникум, после чего работал электромонтером четвертого разряда в сортопрокатном цехе Череповецкого металлургического комбината (ныне в составе ПАО "Северсталь").
В 1990-1992 гг. проходил срочную военную службу. Затем вернулся на Череповецкий комбинат, где до 1995 г. работал электромонтером.
В 1998-1999 гг. был инженером-программистом в сортопрокатном цехе, в 1999 г. был назначен руководителем проекта дирекции "Северстали" по стратегическому планированию.
В 2000-2006 гг. - заместитель начальника сортопрокатного цеха по техническому обслуживанию Череповецкого металлургического комбината.
В 2006-2010 гг. был генеральным директором ООО "Электроремонт" (в составе ОАО "Северсталь").
С марта 2010 г. по март 2012 г. - первый заместитель мэра г. Череповца Олега Кувшинникова.
С 26 марта 2012 г. - заместитель губернатора, с 29 октября 2012 г. по 12 июня 2014 г. - первый заместитель губернатора Вологодской области Олега Кувшинникова.
С 12 июня 2014 г. по 3 ноября 2016 г. - заместитель полномочного представителя президента РФ в Северо-Западном федеральном округе (полпредство в этот период возглавляли Владимир Булавин, затем Николай Цуканов).
В 2016-2017 гг. - мэр Вологды. 2 ноября 2016 г. депутаты Вологодской городской думы единогласно избрали Андрея Травникова главой города. 7 ноября того же года он официально вступил в должность.
С 2017 г. руководит Новосибирской областью.
6 октября 2017 г. указом президента РФ Андрей Травников был назначен врио губернатора Новосибирской области. Сменил во главе региона Владимира Городецкого.
9 сентября 2018 г. был избран губернатором Новосибирской области на прямых выборах (баллотировался от "Единой России"). По итогам голосования получил 64,52% голосов. Второе место занял депутат Госдумы РФ от ЛДПР Дмитрий Савельев (17,35%). Инаугурация состоялась 14 сентября того же года.
10 сентября 2023 г. Андрей Травников вновь победил на выборах губернатора Новосибирской области, набрав 75,72% голосов избирателей (был выдвинут "Единой Россией"). Его ближайший соперник, депутат заксобрания региона Роман Яковлев (КПРФ), получил 10,72%. 15 сентября того же года Травников вступил в должность.
Член высшего совета "Единой России". Член комиссии генсовета партии по образованию и науке (с ноября 2021 г.). Секретарь политсовета регионального отделения "Единой России" в Новосибирской области.
Член президиума Госсовета РФ. С декабря 2020 г. - председатель комиссии Госсовета по направлению "Наука".
Действительный государственный советник РФ II класса (2016).
Награжден орденом Дружбы (2021).