Родился 19 июня 1976 года в Кишинёве. В 13 лет начал учиться играть на аккордеоне, но затем перешёл на гитару, так как аккордеон было тяжело выносить во двор. Тогда же научился брать первые аккорды и исполнять «дворовый» репертуар[1]. По словам самого А. Леонтьева, научился хорошо играть на гитаре благодаря группе «Кино», а когда Цой погиб, пережил два года откровенного фанатизма по нему, одевался во всё чёрное. Затем, когда вышел Black Album группы «Metallica», увлёкся её творчеством и задался целью снять все гитарные и басовые партии с этого альбома. Позднее увлёкся творчеством треш-метал групп «Slayer» и «Megadeth».
После окончания школы приехал в Санкт-Петербург, поступил в Ветеринарный институт, из которого ушёл, не доучившись один год, поняв, что не хочет в дальнейшем работать по специальности. В Петербурге встретил будущих коллег по «Кукрыниксам». Практически одновременно с этим познакомился с Михаилом и Алексеем Горшенёвыми. До этого Леонтьев увлекался музыкой в стиле хэви-метал, но после посещения концерта «Короля и Шута» решил играть что-то подобное.
В 1997—2001 годах был участником группы «Кукрыниксы». Написал несколько песен, вошедших в дебютный альбом коллектива.
Первое выступление с группой «Король и Шут» состоялось летом 1996 года. Леонтьева попросили помочь с исполнением акустической программы, так как одного гитариста для этого явно не хватало. С тех пор Леонтьев время от времени появлялся на выступлениях группы в качестве сессионного гитариста. С лета 2000 года играл практически на каждом концерте «Короля и Шута», одновременно продолжая быть участником «Кукрыниксов».
28 января 2001 года на сайте «Кукрыниксов» появилась новость, что Леонтьев окончательно ушёл из «Кукрыниксов» в группу «Король и Шут».
У меня несколько разошлись взгляды с Лёшкой Горшком, поскольку он больше практиковал образ мачо, такой у него выстроился имидж. Это на сто процентов проявилось на «КИНОпробах». Когда мы там играли, я понял, что мне с Лёхой на одной сцене делать нечего. Меня колбасит по-панковскому, по-Михинскому, и с Лёхой мне не по дороге. И я сказал, что остаюсь навсегда в «Короле и Шуте». А «Король» уже очень плотно и серьёзно занимался делом, я же тороплюсь жить, хочу, чтобы всё происходило быстрее, хочу получить всё, много и сразу. Не в смысле денег, а вообще, жизни.
В 2003 году принял участие в проекте «Рок-группа», в песне «Кошка», вместе с некоторыми членами группы «Король и Шут».
В начале 2006 года, после ухода из группы Александра Балунова, выступал в составе «Короля и Шута» в качестве бас-гитариста. В новом амплуа сыграл на двух концертах: 3 февраля на фестивале «Чартова дюжина» и 13 февраля на концерте памяти Башлачёва, а также записал басовые партии к песням «Марионетки», «Писатель Гудвин» и «Матёрый волк» с альбома «Продавец кошмаров». Покинул группу в конце февраля: из-за смерти отца на него свалился семейный бизнес, который оказался несовместимым с музыкой. В качестве сессионного музыканта помог в записи гитарных партий к альбому «Продавец кошмаров»: звучание его инструмента можно услышать во всех композициях альбома, кроме «Плясок на могиле».
В том же году принял участие в записи песни «Вертикаль» группы «Кукрыниксы» из альбома «Шаман», а в 2008 году принял участие в нескольких концертах коллектива.
17 августа 2011 года было объявлено о возвращении Леонтьева в «Король и Шут». С этого времени был не только гитаристом, но и вторым вокалистом группы.
С 2013 года официально стал эндорсером всемирно известной марки Dean Guitars, эксклюзивно представляемой в России компанией MixArt. Выбрал электрогитару Dean USA ML 1000 MWH.
После смерти Михаила Горшенёва в рамках тура «Прощание», выступал как основной вокалист группы «Король и Шут». 13 октября 2013 года выступил на юбилейном концерте «Кукрыниксов» в Москве.
С окончанием 2013 года заявил о прекращении работы «Короля и Шута» и создании нового проекта, который получил название «Северный флот». Леонтьев является лидером группы, вокалистом, автором текстов и музыки, гитаристом.
Женат во второй раз. От второго брака имеет четверых детей: Марию, Егора, Варвару и Гордея.
