Родился 22 августа 1954. Старший сын председателя Сельхозтехники Горьковской области и зав.отделом сельского хозяйства Горковского обкома, погибшего в 1982 году.
         Окончил Горьковский политехнический институт.
         В 1980 году познакомился с Борисом Немцовым.
         В 1982 году был арестован вместе с братьями Сергеем и Александром и их приятелем Юрием Кошелевым по делу "о распостранении порнографии" (видеокассеты фильмов типа "Эммануэль", "Секс-концерт", "Сука", "Жеребец" и т.п.). По словам бывшего областного прокурора Леонида Видонова, инициатором дела Климентьева был областной КГБ. 21 августа 1982 был осужден на 5 лет по обвинению в приготовлении к мошенничеству в особо крупных размерах (у него было найдено шулерское приспособление в виде очков для подглядывания  карт у противника) плюс 3 года за порнографию. Против обыкновения был применен метод сложения сроков (а не поглощения большим сроком меньшего). В 1996 судимость была "погашена".
         Был владельцем казино "Рокко" и супермаркета "Европа" в Нижнем Новгороде. Президент российско-норвежской компании "Aroco".
          В октябре 1993 активно поддержал указ президента Ельцина № 1400 и выступил против позиции Верховного Совета РФ.
         Осенью 1993 финансировал предвыборные кампании Бориса Немцова в Совет Федерации и Татьяны Черторицкой в Госдуму. Объем затрат составил около 1000млн. руб. (Ъ, 16 января 2001 ).
         В 1994 году поссорился с Немцовым, пытался создать в1995 г. партию "Правый берег".
         В октябре 1995 года был арестован в Ташкенте. Весной 1996 года начался процесс по делу "навашинских миллионах".
         Находясь под арестом, баллотировался в Госдуму, проиграл Ольге Беклемищевой (существует версия, что результаты были подтасованы). В 1996  баллотировался в городскую думу Нижнего Новгорода.
         В апреле 1997 года Нижегородским областным судом А.Климентьев и проходящий по этому делу Кисляков были признаны виновными в присвоении и растрате $2 млн. 462 тыс. (ст.160.3 УК РФ). Из 11 эпизодов суд принял во внимание только один. Климентьев получил полтора года. Он был освобожден в зале суда, т.к. отсидел этот срок в СИЗО.
         В январе 1998 года начал сбор подписей для регистрации кандидатом на пост главы администрации г.Нижнего Новгорода.
         29 марта 1998 года был избран мэром Нижнего Новгорода, набрав 33,4 процента голосов избирателей.
         30 марта 1998 года председатель Центризбиркома А.Иванченко заявил, о многочисленных нарушениях во время избирательной кампании в городе. В частности, были названы: 1) агитация должностных лиц (Климентьева поддерживал депутат ГД В.Семаго); 2) заведомо неисполнимые обещания (снижение цен); 3) публикация в СМИ социологических опросов без выходных данных. Об озабоченности результатами выборов президента Ельцина заявил его пресс-секретарь С.Ястрежембский. Для выяснения обстоятельств проведения выборов в Нижний Новгород был направлен заместитель руководителя администрации президента Евгений Савостьянов .
         31 марта 1998 года областная избирательная комиссия отменила результаты выборов. Климентьев заявил о намерении обжаловать в суде постановление избирательной комиссии. Он также заявил, что заявление о неисполнимости обещания о снижении цен, свидетельствует о том, что власти не верят в это. Климентьев задал риторический вопрос о том, как власти в этом случае могут руководить государством.
         2 апреля 1998 года Климентьев был арестован в зале суда, где он выступал в качестве обвиняемого по делу о хищении валютного кредита Минфина, выделенного принадлежавшему Климентьеву навашинскому судостроительному заводу "Ока". По версии следствия, на судостроительные проекты Климентьева у Минфина РФ был выбит кредит в $18 млн под гарантии областного бюджета. В январе 1995 года Минфин выяснил, что часть кредита ушла в Норвегию на счета климентьевских фирм. Было возбуждено уголовное дело. Борис Немцов начал называть бывшего друга расхитителем. (Власть, 18 июля 2005)
        Был препровожден в следственный изолятор УВД Нижегородской области. Мера пресечения  ему была изменена судьей Василием Поповым "за провокацию массовых беспорядков" (до этого с Климентьева была взята подписка о невыезде).
         В мае 1998 года суд Нижнего Новгорода отклонил иск Климентьева против окружной избирательной комиссии, признавшей итоги выборов недействительными.
         25 мая 1998 года по делу о "навашинских миллионах" приговорен к 6 годам лишения свободы.
         29 июля 1998 года был зарегистрирован кандидатом на предстоящих 27 сентября 1998 года выборах мэра Нижнего Новгорода, поскольку Верховным судом еще не было вынесено решение по аппеляции Климентьева.
      10 августа 1998 года судебная коллегия по уголовным делам Верховного Суда РФ оставила в силе решение Нижегородского облсуда, приговорившего Климентьева к шести годам лишения свободы с конфискацией имущества. Адвокаты Климентьева выразили намерение обратиться в Европейский международный суд.
         В октябре 1998 года норвежская газета "Дагбладет" выступила с сообщением, что в банке Ставангера обнаружены огромные суммы долларов, принадлежащие Андрею Климентьеву. Жена Климентьева опровергла эту информацию.
         В феврале 1999 года Нижегородская областная прокуратура приняла решение об ошибочности предъявленного Климентьеву в 1982 году обвинений в распостранении порнографии и картежных махинациях.
        В октябре 2000 был условно досрочно освобожден из заключения. После освобождения заявил о намерении вернуться в политику и балотироваться на выборах губернатора Нижегородской области летом 2001 года. 15 января 2001 подтвердил намерение баллотироваться на пост губернатора Нижегородской области под лозунгом "Сильному - работу, слабому - заботу", с которым победил на выборах в 1998.
       В апреле 2001 года был зарегистрирован в качестве кандидата на пост губернатора Нижегородской области. Кандидатом был также зарегистрирован родной брат Климентьева Сергей.
        21 мая 2001 появилось сообщение, что после допроса в налоговой полиции была задержана бывшая жена Климентьева Оксана, которая вела его дела во время заключения. По словам Климентьева, это было сделано, потому что его "пытаются сломать". (Коммерсант, 22 мая 2001) . Также заявил, что Оксана "томится в застенках ФСБ" и что к ее исчезновению причастны полномочный представитель президента в Приволжском округе Сергей Кириенко и губернатор области Иван Скляров. ( КоммерсантЪ, 23 мая 2001).
        Через четыре часа после пресс-конференции Оксана нашлась и сделала заявление о своем участии в выборах губернатора. Бывшая жена предпринимателя заявила, что ее никто не похищал и не арестовывал - просто она на время решила уединиться для того, чтобы обдумать сложившуюся ситуацию. (Страна.ру, 23.05.01) Однако избирком не зарегистрировал Малкину в связи с тем, что она не достигла 30-летнего возраста.
        Предвыборная кампания Климентьева строилась на напоминаниях о 1998 г., когда "власти не дали народу выразить свою волю". При этом против самого Климентьева велась жестокая информационная война: в городе появлялись плакаты, на которых были изображены проститутки, бандиты и гомосексуалисты, призывающие голосовать за него, по телевидению был показан фильм, в котором рассказывалось, как Климентьев отсудил ребенка у бывшей жены Оксаны и совсем не заботился о его воспитании. (Власть, 16 июля 2002 )
        На губернаторских выборах 15 июля 2001  занял пятое место из одиннадцати, набрав 10,54% голосов.
      3 июля 2002 выдвинул свою кандидатуру на пост мэра Нижнего Новгорода на выборах 15 сентября 2002 и сдал денежный залог. 11 июля 2002 был зарегистрирован в качестве кандидата.
       В интервью журналу "Власть" сказал, что уверен в победе и в поддержке президента Путина. При этом Климентьев добавил: "В эту кампанию он (т.е. Путин) кое-что узнает, поэтому советую Кириенко и Немцову сидеть тихо. Ни Путин, ни Касьянов не знают, что со мной творили эти подонки." (Власть, 16 июля 2002 )
       В начале августа 2002 г. нижегородское отделение Института социологии РАН провело опрос, согласно которому Климентьев занимал первую позицию в рейтинге кандидатов: более 18% потенциальных голосов против 17% у Вадима Булавинова. При этом кампания Климентьева, по мнению сотрудников избиркома, 
была самой выверенной и законопослушной. Он буквально по каждому шагу консультировался с командой юристов, не давая никаких поводов для снятия своей кандидатуры. (Коммерсант, 16 августа 2002)
       29 августа 2002 два кандидата в мэры - Юрий Сентюрин и Михаил Дикин - уведомил городской избирком об отказе от участия в выборах. По мнению газеты "Коммерсант", это было сделано по настоянию полпреда президента в Приволжском ФО Сергея Кириенко, перед которым Кремль поставил задачу не допустить во власть Климентьева. Оба бывших кандидата призвали отдать голоса Вадиму Булавинову. (Коммерсант, 30 августа 2002 )
      Вечером 14 сентября 2002, меньше, чем за сутки до выборов мэра Нижнего Новгорода, Климентьев был лишен кандидатской регистрации. За день до этого его противникам удалось найти свидетельницу, которая рассказала на суде, что она внесла в избирательный фонд Климентьева деньги, переданные ей третьим лицом (это является нарушением правил выборов). (Власть, 23 сентября 2002 )
       15 сентября 2002 г. на выборах 30,35% избирателей проголосовали против всех (всего лишь на 0,5% меньше, чем занявший второе место Булавинов и на 1,05% меньше, чем занявший первое Лебедев).
        1 октября 2002 г. Климентьев подал ходатайство в Нижегородский районный суд с требованием остановить подведение горизбиркомом итогов второго тура выборов мэра Нижнего Новгорода. Он утверждал, что 80% избирательных бюллетеней с пометкой в графе "против всех" были во время подсчета голосов в первом туре выборов незаконно признаны недействительными. В штабе Климентьева откровенно говорили, что Нижегородский суд не удовлетворит жалобу, но его решение необходимо для того, чтобы появилась возможность подать жалобу в Европейский суд". (Коммерсант, 9 октября 2002) 
     5 сентября 2003 г. Климентьев заявил о своем намерении баллотироваться в Государственную думу России по 120-му одномандатному избирательному округу. ( Газета. Ru, 5 сентября 2003)  
     В марте 2005 г. заявил о своем участии в выборах мэра Нижнего Новгорода, назначенных на 16 октября 2005 г. 
     Летом 2005 года стало известно, что агрофирма "Пермеево", которую учредил Климентьев, взяла в аренду 40 000 га земли в Большеболдинском и Лукояновском районах Нижегородской области. Климентьев заявил, что вложил около 40 млн руб. в покупку новой сельхозтехники. Кроме того, в "Пермеево" было 300 овец, 250 коров, 15 лошадей и 2000 гусей. В администрациях Большеболдинского и Лукояновского районов сообщили, что Климентьев взял в аренду у пайщиков шести разорившихся колхозов около 9000 га пахотных земель в Лукояновском и 5000 га в Большеболдинском районах. (Ведомости - Нижний Новгород 03.06.2005) 
     В августе 2005 г. сообщил, что о своем решении баллотироваться или нет на пост мэра объявит после выдвижения основных кандидатов: "Сейчас товарищ Путин ведет нас к неокоммунизму, а я не хочу стать винтиком этой неокоммунистической машины и в связи с этим не проявляю особой прыти, как раньше. Если приму решение - 50% голосов будет мне обеспечено, как всегда. Мобилизация пройдет в трехдневный срок, потому что раскручиваться особо мне не надо". (Коммерсант, 20 августа 2005)
     7 сентября 2005 г. объявил, что не будет участвовать в выборах. Решение мотивировал "полувоенным режимом в стране" и "беспределом в Нижнем": "Если я буду мэром города, то надо будет вступать в "Единую Россию", а это для меня неприемлемо. А если идти на выборы, их надо проигрывать, для меня проигрыш тоже неприемлем". Он предположил, что в случае его участия в выборах команда полпреда президента в Приволжском федеральном округе Сергея Кириенко сделала бы все, чтобы ему помешать. "Пусть они сами с собой играют в игрушки, пусть, например, КПРФ их развлекает. А я пойду в Госдуму, обязательно против "Единой России", скорее всего, с одной из партий патриотического толка. Там и срубимся с господином Кириенко". (Коммерсант, 8 сентября 2005)      
     

      Состоял в четырех браках. Последняя жена, Оксана Климентьева, с отличием окончила физико-математический факультет Горьковского гос. университета, работала секретарем-референтом Нижегородской ярмарки, в нижегородском бюро ВГТРК, пресс-секретарем Нижегородского областного Совета. Является владелецей супермаркетов "Европа" и "Нижегородский универсам". После развода взяла девичью фамилию - Малкина.
   
         Двое взрослых сыновей от прежних браков (один живет с матерью в Израиле, другой в России), сын Андрей 1995 г. р. от последнего брака. 
     
     В 2005 году в Нижегородской области Климентьеву принадлежали два магазина - "Европа" и Нижегородский универсам, Дом обуви на улице Горького, ночной клуб "Рокко", завод по производству пиломатериалов "Парма-Лес", завод по производству торгового оборудования "АКМЕ". Годовой оборот всех компаний, по данным Климентьева, - около 1 млрд руб. (Ведомости - Нижний Новгород 03.06.2005)