Олександр народився в селі Калитинка Вінницької області. Навчався у Технологічно-промисловому фаховому коледжі Вінницького національного аграрного університету. Змалечку займався тенісом і дзюдо. Був кандидатом в майстри спорту з дзюдо. Мав багато нагород медалей, кубків, грамот. Був мотоциклістом. Одружився, виховував сина, якого обожнював. Жив із сім’єю у Вінниці. Останнім місцем роботи була компанія «Авангард дистрибуції», де він обіймав посаду експедитора.
Під час повномасштабної війни Олександр приєднався до лав Десантно-штурмових військ ЗСУ. Службу проходив у 25-й окремій повітрянодесантній Січеславській бригаді.
«Саша завжди був мужнім і хоробрим, тому одним з перших пішов на штурм, казав: «Хто, як не я? А як по-іншому?». Остання розмова з ним була 10.07, ще наостанок почув перше слово «тато» від сина, казав: «Син – богатир, а дружина – модель. Не хвилюйтеся за мене, ви мої янголята, які мене будуть оберігати». Досі не вірю, що це все насправді, шукаю його в кожному обличчі, пройшла таке пекло пошуку і до останнього вірила, що обійму його живого... Ми ним пишаємося. Він був дуже добрим, щирим, водночас мужнім і сильним. Син – його маленька копія. Він завжди казав, що я «пробивна», тому я все буду робити для сина, для нас, щоб він з неба нам посміхався і гордився нами…» – поділилася дружина полеглого захисника Аліна.
Посмертно солдат Василенко Олександр Віталійович нагороджений орденом «За мужність» ІІІ ступеня.
Поховали воїна в рідному селі Калитинка.
Вдома на Олександра чекали дружина і син.
