Співак народився 17 серпня 1968 року в Самборі Львівської області. Пізніше його родина переїхала у м. Новояворівськ, де він і почав свій творчий шлях. Матір була вчителькою музики, Андрій закінчив музичну школу (клас фортепіано).
Більш за все, творчість Андрія Кузьменка пов’язана з гуртом “Скрябін”, який виник 1989 року в містечку Новояворівськ, Львівської області.
Як відомо, 2 лютого 2015 року, на 86 км траси Кривий Ріг — Кіровоград відбулося зіткнення позашляховика Toyota Sequoia, за кермом якого перебував співак, і молоковоза ГАЗ-53. Від отриманих травм Андрій Кузьменко загинув на місці. Кузьменко повертався з Кривого Рогу, де напередодні його гурт дав концерт.
Співака поховали у передмісті Львова на Брюховицькому кладовищі у родинному склепі.