Родился 9 ноября 1954 г. в г. Молотове (ныне Пермь).
В 1976 г. окончил Пермский государственный университет им. А. М. Горького (ныне Пермский государственный национальный исследовательский университет) по специальности "экономист".
Доктор экономических наук. В 1981 г. в Научно-исследовательском институте экономики строительства (НИИЭС) Госстроя СССР защитил кандидатскую диссертацию "Системные преобразования социально-экономического пространства проблемных территорий". В 2006 г. в Институте системного анализа Российской академии наук защитил докторскую диссертацию на тему "Системные преобразования социально-экономического пространства проблемных территорий".
С 1976 по 1978 г. - инженер-экономист Пермского областного управления сельского строительства.
Затем был аспирантом, младшим научным сотрудником сектора международного сотрудничества НИИЭС Госстроя СССР в Москве.
После защиты диссертации вернулся в Пермь.
С 1981 по 1992 г. работал на экономическом факультете Пермского государственного университета ассистентом, преподавателем, заведующим кафедрой экономики, учета и анализа хозяйственной деятельности в строительстве. Был председателем профсоюзного бюро. Являлся заместителем председателя художественного совета университета, членом правления студенческого клуба. В 1988 г. стал одним из организаторов консультационно-учебного бюро.
Работал внештатным корреспондентом областных газет "Звезда" и "Молодая гвардия". Его юмористические рассказы и фельетоны, написанные в т. ч. в соавторстве, печатались в "Литературной газете", издании "Социалистическая индустрия", журнале "Крокодил". Вел программу на пермском телевидении.
До 1991 г. был членом КПСС.
С 1990 по 1993 г. - депутат Пермского областного Совета народных депутатов, член президиума Совета, председатель постоянной комиссии.
В 1992-1999 гг. - директор Межотраслевого института региональных исследований (Пермь), генеральный директор акционерное общество закрытого типа "Ассоциация содействия развитию предпринимательства "КУБ" (с 1995 г. - Корпорация "КУБ"; доля в корпорации принадлежала кипрской фирме Bikel Enterprises Ltd.).
С июля 1995 г. был также председателем правления Ассоциации содействия развитию Прикамья.
Входил в органы управления ряда коммерческих организаций.
В 1994-1999 гг. - депутат Законодательного собрания Пермской области I и II созывов, председатель комитета по региональной политике и внешним связям. Избирался 20 марта 1994 г. по округу №13 (часть Свердловского района Перми), 14 декабря 1997 г. - по избирательному округу №39 (г. Кудымкар, часть Кудымкарского района и Юсьвинский район). Досрочно сложил депутатские полномочия 31 декабря 1999 г. в связи с избранием в Государственную думу РФ.
В начале 2000 г. стал доверенным лицом кандидата на пост президента РФ Владимира Путина.
В 1999-2012 гг. – депутат Государственной думы Федерального собрания РФ III, IV, V и VI созывов.
19 декабря 1999 г. был избран депутатом Госдумы РФ III созыва по Коми-Пермяцкому одномандатному избирательному округу №216 (Коми-Пермяцкий АО). Был выдвинут группой избирателей, по итогам голосования получил 60,21% голосов, второе место занял главврач окружной больницы Виталий Козловский (8,93%; выдвинут группой избирателей). В январе 2000 г. вошел в комитет по делам Федерации и региональной политике, весной 2000 г. возглавил его подкомитет по социально-экономическому развитию регионов и межрегиональным связям. Был членом депутатской группы "Регионы России (Союз независимых депутатов)", с 2002 г. - заместителем руководителя группы Олега Морозова.
7 декабря 2003 г. стал депутатом Госдумы IV созыва. Был избран по Коми-Пермяцкому одномандатному округу №216, набрав 62,74% голосов (баллотировался в порядке самовыдвижения). Второе место занял предприниматель, самовыдвиженец Анатолий Никитасенко с результатом 10,38%.
В 2004-2005 гг. Андрей Климов возглавлял подкомитет по социально-экономическому развитию регионов и межрегиональным связям комитета по делам Федерации и региональной политике. 19 октября 2005 г. перешел в комитет по международным делам, стал заместителем председателя комитета по международным делам Константина Косачева (курировал европейское направление). Был заместителем руководителя депутатской группы "Регионы России". В 2004 г. избран руководителем парламентской группы по связям со странами Бенилюкса (Бельгия-Люксембург-Нидерланды).
Член Всероссийской политической партии "Единая Россия" (с 2007 г.).
2 декабря 2007 г. избран в Государственную думу V созыва в составе федерального списка кандидатов партии "Единая Россия" (баллотировался под восьмым номеров в региональной группе №26, Пермский край). С 16 января 2008 г. был заместителем председателя комитета по международным делам. Был сопредседателем Комитета парламентского сотрудничества Россия-ЕС и главой постоянной Российской парламентской делегации при Европарламенте. Входил во фракцию "Единая Россия".
4 декабря 2011 г. вновь стал депутатом Госдумы РФ VI созыва по списку партии "Единая Россия" (третий номер в региональной группе №27, Пермский край). В Думе был сначала заместителем, а с 13 марта 2012 г. - первым заместителем председателя комитета по международным делам. Первый заместитель фракции "Единая Россия". Депутатские полномочия были прекращены досрочно 10 июля 2012 г. в связи с переходом в Совет Федерации РФ.
C 2012 по 2016 г. являлся членом президиума генсовета "Единой России", курировал международную деятельность партии. C февраля 2016 г. был советником председателя высшего совета "Единой России" Бориса Грызлова.
С 2012 г. по н. в. - член Совета Федерации Федерального собрания (СФ) РФ (сенатор) от Пермского края.
2 июля 2012 г. губернатор Пермского края Виктор Басаргин подписал указ о назначении Андрея Климова сенатором - представителем исполнительной власти региона. Впоследствии Андрей Климов дважды был переназначен на пост: 18 сентября 2017 г. новым главой края Максимом Решетниковым, 7 октября 2020 г. - Дмитрием Махониным.
21 ноября 2012 г. возглавил постоянную делегацию СФ при Европарламенте. Был главой российских делегаций на заседаниях Межпарламентского союза, Парламентской ассамблеи ОБСЕ и др. С 2012 г. - член постоянного Комитета Международной конференции азиатских политических партий, с 2014 г. - член бюро постоянного Комитета по вопросам мира и безопасности Межпарламентского союза. С марта 2015 г. руководит подкомитетом комитета по международным делам по межпарламентскому сотрудничеству со странами БРИКС.
С 29 октября 2012 г. по октябрь 2020 г. - заместитель председателя комитета Совфеда по международным делам. С 14 июня 2017 г. - председатель временной комиссии СФ по защите государственного суверенитета и предотвращению вмешательства во внутренние дела РФ.
11 октября 2018 г. утвержден главой комиссии президиума генсовета партии "Единая Россия" по международным вопросам. На этом посту сменил депутата Госдумы Сергея Железняка.
До декабря 2021 г. занимал пост заместителя секретаря генерального совета "Единой России" Андрея Турчака.
С ноября 2021 г. - заместитель председателя комиссии генсовета партии "Единая Россия" по международному сотрудничеству и поддержке соотечественников за рубежом.
С декабря 2021 г. - член бюро высшего совета партии "Единая Россия".
Почетный профессор Пермского государственного университета.
Член Совета по внешней и оборонной политике (с 2004 г.).
Председатель правления российского парламентского Европейского клуба.
Награжден орденами Александра Невского (2022), Почета (2004), Дружбы (2017), медалью "За трудовую доблесть" (1986). Командор ордена Заслуг Великого Герцогства Люксембургского (2006). Имеет благодарность правительства РФ (2016) и Почетную грамоту президента РФ.
Награжден орденом преподобного Сергия Радонежского III степени (Русская православная церковь).
Автор книг "Профессия - депутат" (2003), "Двадцать лет спустя. Депутатские заметки на полях недавней истории" (2012), "Воспоминания о юморе" (2013) и др.