Уроженец с.Халитово Кунашакского района Челябинской области. Русский. Образование среднее. Холост.
В Чечне - командир отделения разведки ВВ МВД (в/ч 3499).
В 1994 году закончил среднюю школу с.Халитово и поступил в Челябинский педагогическо-индустриальный техникум.
28 июня 1995 года Ленинским РВК г.Челябинск был призван в ряды Вооруженных сил РФ.
Службу проходил в разведывательной роте спецназа дивизии МВД имени Дзержинского.
С марта 1996 года - Чечня.
19 августа 1996 года погиб в бою в г.Грозный.
За мужество и отвагу, проявленные при выполнении задания, Указом Президента РФ награжден орденом Мужества (посмертно).
Похоронен 26 августа 1996 года на сельском кладбище с.Халитово Кунашакского района Челябинской области.
На здании Тахтапымской средней школы установлена мемориальная Доска памяти.
Всего полсрока успел прослужить в армии Андрей Василенко.
Из них с начала марта 1996 года - в Чечне.

В последнем письме матери он писал:
«Здравствуй, мамуля! Поздравьте меня, я получил звание сержанта... Всем привет друзьям, знакомым. Скоро увидимся... 31 июля. Хасавъюрт, Чечня».
В этом письме были фотографии. На одной он - после очередного задания.
Надпись: «Ну надо же, вернулся!» Та же дата - в письме девушке: «Хочу обрадовать тебя. Нас выводят из Чечни 25 августа. Потому приеду в отпуск. Когда увижу свой халитовский вокзал, то, наверное, в обморок упаду. Честно, честно!...»
Упал Андрей. Но не в обморок от встречи с родными местами. А от пули чеченского автоматчика.

Из рассказа командира разведвзвода, сопровождавшего «груз-200»:
«...19 августа в Грозном при разблокировании КПП разведгруппа попала в засаду. БТР был обстрелян. Андрею пуля попала между пластинами бронежилета. Он только и успел прошептать: «Больно!»
Поведал о том, как это было, тете Андрея, выезжавшей на опознание в Ростов, его друг Алексей, бывший с ним в том последнем бою. Сам он был тогда контужен, а Андрей умер у него на руках.
«Ранило водителя БТР,- рассказывал Алексей. - Андрей его вытащил. Разведку накрыли массированным огнем. Чтобы дать возможность укрыть раненых сослуживцев, Андрей прикрыл ребят огнем. Но тут случилось непоправимое».
«О таких людях, как сержант Василенко, всего и не расскажешь,- говорил на траурном митинге боевой офицер С.Бабиченко, бывший командир Андрея, доставивший его тело в родное село. Мы убедились, что это был человек и боец с большой буквы. Он был достоин надеть краповый берет. Посмертно его представили к ордену Мужества.
После учебы Андрей был в элитном подразделении спецназа - в разведке. Не раз подходил ко мне с вопросом: «Когда мы - в Чечню?» Он думал всегда о братках своих, что там воюют. И вот - спецкомандировка. Отделение разведки, которым командовал Андрей, было храбрым, на первом месте - честь и достоинство бойца спецназа, а уж потом вопрос жизни».
Андрей с малых лет готовил себя к серьезной жизни. Школу закончил без троек, много занимался спортом, ходил в секцию восточных единоборств.
«Он на проводах еще не знал точно, в какие войска попадет, - вспоминали друзья,- но догадывался, куда его возьмут». Попал Андрей Василенко в знаменитую дивизию МВД имени Дзержинского, как в свое время попал в нее его сверстник и земляк из села Сарино Кунашакского района Даниль Абдуллин. Судьбы обоих парней - саринского и халитовского -оказались схожими. Оба одного года рождения. Оба родились в июне. Оба служили в одной дивизии и погибли в одном году.
 В 1996-м...
«Как всегда, погиб лучший из лучших», -говорил при прощании с Андреем райвоенком. То же говорили на похоронах всех ребят, погибших в Чечне, их односельчане: «Видно, и там, на небесах, Богу плохие не нужны. Он забирает к себе только лучших».
Андрея Василенко провожало в последний путь все Халитово, приехали люди и из других, соседних деревень...
Андрей лежал в оцинкованном гробу,отрешенный в свои 19 лет от мирской жизни.
И никто не мог поверить, что этот красивый, умный, добрый и веселый парень никогда уже не увидит солнце, не пройдет по улицам родного села, не поприветствует всех, кого встретит на своем пути, не возьмет в руки гитару и не споет.
Андрей не только играл на гитаре. Он пытался сочинять и стихи. В одном из писем девушке написал такие строчки:

Она, Аля, горько плакала на похоронах Андрея. Так же горько оплакивала его другая девушка, которой он был тоже дорог. И там, и тут - разбитые девичьи мечты. Что уж говорить о родителях Андрея, младшей сестренке? Из окаменевшего отца вообще невозможно было вытянуть ни слова. Осталась ему от сына только гитара, которую Андрей попросил сохранить до возвращения с войны. И, наверное, никто не сможет объяснить, почему Андрей в своей записной книжке написал:
«ЕСЛИ НАС ЖДУТ, МЫ ВОЗВРАЩАЕМСЯ С ТОГО СВЕТА...»
Или предчувствовал что-то?...
Памяти Андрея Василенко была посвящена статья Л.Хисматуллиной «К ордену - за мужество. Посмертно», напечатанная в районной газете «Знамя труда» 10 сентября 1996 года. Отрывки из этой статьи были использованы нами при подготовке материала, посвященного памяти Андрея Василенко.