Служил в царской армии, унтер-офицер. После Октябрьской революции вступил в Красную Гвардию.

Член Компартии с 1918 г.

Командир взвода красногвардейского отряда в Бухаре

В 1918 году Величко пошел на службу в Рабоче-крестьянскую Красную Армию. Участвовал в боях Гражданской войны, будучи комиссаром роты отдельного Самаркандского батальона, помощником командира батальона, командиром батальона 1-го Туркестанского стрелкового полка 1-й Туркестанской стрелковой дивизии.

Принимал активное участие в разгроме басмаческих бандформирований в Средней Азии, особо отличившись во время боев в районе станций Байрам-Али, Душан и Каахка. Приказом Революционного Военного Совета Республики № 184 от 5 сентября 1922 года командир 1-го батальона 1-го Туркестанского стрелкового полка Алексей Величко был награжден орденом Красного Знамени РСФСР.

Командир 1-го Туркестанского стрелкового полка.

После окончания войны Величко продолжил службу в Рабоче-крестьянской Красной Армии. Окончил курсы "Выстрел" и Военную академию РККА имени М. В. Фрунзе.

В годы Великой Отечественной войны командовал сначала Таллинским, затем Тюменским военными пехотными училищами. Окончил Военную академию Генерального штаба, после чего командовал 122-й стрелковой дивизией, принимал участие в освобождении Карелии и Венгрии.
В 1946-55 - начальник Управления боевой и физической подготовки Прикарпатского военного округа.
В 1955 году уволен в запас.

Награжден орденом Ленина и четырьмя орденами Красного Знамени, орденом Красного Знамени Хорезмской НСР, рядом медалей.

генерал-майор (2 ноября 1944 года)