Випускник Харківського інституту танкових військ, начальник служби радіаційного, хімічного та біологічного захисту – начальник служби екологічної безпеки військової частини 3037 (Донецьк) Східного оперативно-територіального об’єднання Національної гвардії України. Майор Андрій Величко зарекомендував себе грамотним та підготовленим офіцером. Він завжди відповідально ставився до виконання службових обов’язків, виявляючи старанність, наполегливість і розумну ініціативу.

14 травня 2014 року десятки невідомих озброєних осіб оточили та заблокували військове містечко № 20 в/ч 3037 у Донецьку. Майор Величко виконував завдання з розвідки за діями озброєних проросійськи налаштованих громадян та їх переміщенням навколо військового об'єкту.

Діючи в складі військового оперативного резерву полку, у червні 2014 року під час оборони від проросійських бойовиків будівлі Донецької обласної прокуратури майор Величко зазнав важкого поранення в руку. Незважаючи на це, він продовжував виконувати службово-бойові завдання, з власної ініціативи брав участь у розвідці, спостерігаючи за діями бойовиків та їх переміщенням. 29 червня частина отримала наказ щодо передислокації до Маріуполя, і Андрій Валерійович допомагав однополчанам покинути військове містечко. Під час штурму частини опинився у полоні банди Безлера (Горлівка).

Коли його відпустили з полону, не мав при собі документів. 17 липня 2014-го зник у місті Красногорівка без документів. З Красногорівки повідомив про себе сестрі, скориставшись телефоном одного з місцевих жителів. Цей же громадянин вказав йому дорогу на село Піски через Старомихайлівку, коли за Величком легковиком «Хюндай Елантра» чорного кольору д/н АН 1654 ЕВ приїхала мати та двоє знайомих. Пополудні 17 липня виїхав з Красногорівки мікрорайон Сонячний д. 9 кв. 38 (без документів), на машині «Хюндай Елантра» АН1654ЕВ чорного кольору, разом з трьома людьми: Лось Володимир, Скоринін Тимур та Величко Ірина. З того часу зникли безвісти. Машину знайшли спалену, без людей. Розстріляну і спалену машину «Хюндай», схожу на ту, якою їхали чотири зниклих, їхні родичі згодом виявили поблизу селища Лозового Ясинуватського району Донецької області.

У вересні 2015 пошукова група забрала з нейтральної зони в посадці між Красногорівкою та Старомихайлівкою трьох вбитих, застрелених у голову.

Лише за три роки було встановлено, що останки розстріляного чоловіка, знайдені у серпні 2015-го у лісопосадці між населеними пунктами Красногорівкою та Старомихайлівкою, належать майору Величку, і у вересні 2017 року його було перепоховано у місті Сєверодонецьку.

За сумлінне виконання службових обов’язків, відданість Військовій присязі та українському народові, зразкове виконання службово-бойових завдань, за особисту мужність і відвагу в складних умовах загрози життю та здоров’ю майор Андрій Величко нагороджений орденом «За мужність» III ступеня (посмертно).