Родился в дворянской семье. Окончил 2-ю Санкт-Петербургскую военную гимназию. В 1875 году окончил Николаевское инженерное училище, сейчас Военный инженерно-технический университет в Санкт-Петербурге. В 1877 году выдержал вступительный экзамен в Николаевскую инженерную академию (ныне Военный инженерно-технический университет), но начавшаяся русско-турецкая война побудила его оставить на время академию и отправиться в действующую армию, где он состоял сначала в 1-м саперном батальоне, затем во 2-м военно-телеграфном парке. Участвовал в разработке Твердицкого перевала между г. Еленой с севера и селением Твердицей с юга Балкан.
После окончания войны осенью 1878 года вернулся в инженерную академию, которую окончил в 1881 первым по успеваемости и его имя было занесено на мраморную доску. Был оставлен при академии преподавателем, занимал должность репетитора по фортификации. В 1883 году был командирован за границу в Берлинский университет для слушания лекций и затем в Германию, Францию, Италию, Англию и Бельгию для практического изучения технического производства. C 1890 профессор Николаевской инженерной академии по кафедре фортификации, оставался на этой должности до начала русско-японской войны. В 1892 и 1893 годах полковник Величко работал в крепостях Ковно и Новогеоргиевске, где заведовал сооружением крепостных железных дорог и принимал участие во всех занятиях гарнизонов. С 1893 — член комиссии по вооружению крепостей, с 1895 — управляющий делами этой комиссии. Участвовал также во многих других комиссиях и комитетах. В 1903 году был назначен помощником главного начальника инженеров.
Автор многих научных трудов по фортификации. В своих работах выступал против применения бронебашенных установок в крепостях. Своими трудами Величко много способствовал образованию русской фортификационной школы, отличающейся сочетанием живой силы с прикрывающими мертвыми массами, стремлением достигнуть безопасности артиллерии с помощью маскировки и передвижения орудий, разработкой путей сообщения в крепостях и вообще организацией крепостных сооружений, наиболее соответствующих активной обороне.
С началом русско-японской войны 12-го февраля 1904 года был назначен генералом для особых поручений при командующем (позже главнокомандующем) силами на Дальнем Востоке Куропаткине. Исполнял различные поручения его по инженерной части, как, например, разработку проектов укреплений Ляояна, Кавлитцунской позиции на р. Ляохе, Инкоу, Ташичао, Хайчена, Айсандцянской и Ляндясяньской позиции, а также (тотчас после оставления Ляояна) Мукдена, Телина, а после мукденских боёв и Харбина.
Генерал-лейтенант (1907). В 1910—1914 состоял председателем редакционного комитета «Военной Энциклопедии» издательства Сытина и редактором, объединяющим все ее четыре отдела.
В годы первой мировой войны Величко с 1914 в распоряжении Главнокомандующего армиями Юго-Западного фронта, затем начальник инженеров 11-й армии, осуществлявшей осаду Перемышля. С 4 марта 1916 — начальник инженеров Юго-Западного фронта. Предложил новую форму инженерного оборудования местности для наступления — «инженерные плацдармы». Впервые такой плацдарм был создан при подготовке брусиловского прорыва. После Февральской революции Величко, заслуженно пользовавшийся крайне высокой репутацией в армии, был 10 мая 1917 назначен на высшую должность полевого инспектора инженерной части в Ставке Верховного главнокомандующего.
В феврале 1918 добровольно вступил в Красную Армию, руководил инженерной обороной Петрограда, с марта 1918 председатель коллегии по инженерной обороне государства при Главном инженерно-техническом управлении РККА, преподавал инженерное дело в Военной академии РККА. С января 1919 — член инженерного комитета ГВИУ. В приказе РВСР № 2731 от 8 дек. 1922 отмечалось, что «громадная работа, проделанная профессором Величко по изучению и использованию опыта мировой войны, дала возможность устранить недочеты прошлых лет при укреплении наших рубежей… Имя профессора Величко останется в истории наряду с самыми крупными именами в области фортификации».
С 1923 — профессор фортификации в Военно-инженерной академии в Ленинграде. Умер в 1927 году.