Родился К.И. Величко 20 мая 1856 г. в с. Короче Курской губернии. Общеобразовательную подготовку получил во Второй Петербургской военной гимназии, по окончании которой в шестнадцатилетнем возрасте поступил в Николаевское инженерное училище. После трех лет обучения и производства в подпоручики был направлен для прохождения службы в 8-й саперный батальон. Человек всесторонне одарённый и талантливый, он решил продолжить обучение и в 1877 г. поступил в Николаевскую инженерную академию. Успешно сдал экзамены, был зачислен ее слушателем, но с началом Русско-турецкой войны 1877–1878 гг. прервал учебу и перевелся в действующую армию. С фронта он вернулся поручиком и с усиленной энергией принялся за обучение. Помимо положенного курса, Константин Иванович самостоятельно изучал богатое наследие фортификаторов западных стран, следил за новинками, что невозможно было без прекрасного знания французского и немецкого языков. «Получив хорошее образование, он еще дополнял его обширной начитанностью по общим военным и специальным инженерным вопросам», – писал о нем М.Н. Богатский.
Академию штабс-капитан К.И. Величко окончил в 1881 г. по I разряду. Его имя было занесено на мраморную доску академии, а сам он был назначен младшим преподавателем в Инженерную академию и училище. В связи с предстоящей преподавательской работой в 1883 г. его командируют за границу: в Германию, Румынию, Францию, Бельгию, Италию. К.И. Величко изучает постановку военно-инженерного дела, анализирует современные тенденции и направления развития европейских школ фортификации, принимая участие в испытаниях с иностранными инженерами, в том числе и в Бухаресте. Неудивительно, что первой его наградой становится иностранная – румынский офицерский крест ордена Короны. Он прослушал курс лекций профессора Гельмгольца по экспериментальной физике в Берлинском университете, курсы лекций по многим другим предметам. Итогом поездки становятся: богатый аналитический материал, опубликованный в четырех его книгах; выработка оригинальной и целостной концепции развития полевой и долговременной фортификации в России. Возвратившись в 1886 г. в академию, штабс-капитан К.И. Величко начинает читать новый специальный курс «Броневые закрытия». С 1888 г. «Инженерный журнал» начал публикацию его первого капитального труда «Исследование новейших средств осады и обороны сухопутных крепостей», открывшего для многих специалистов уникальный талант молодого русского инженера. За эту работу автор был удостоен почётной Михайловской премии.
В 1889 г. ему присваивается звание подполковника, в 1893 г. – полковника. С 1895 г. Константин Иванович становится членом Инженерного комитета Главного инженерного управления, принимает участие в выработке решений по развитию и оснащению крепостей, в том числе и Владивостокской.
В июне 1899 г. полковник К.И. Величко был командирован на Дальний Восток для составления на месте проекта укрепления Квантунского полуострова, города и порта Порт-Артур. По его проекту оборонительный ансамбль крепости должен был состоять из 22 долговременных позиций для береговых и девяти сухопутных артиллерийских батарей, восьми фортов, 42 других инженерных сооружений, в том числе и шести с половиной километров непрерывного земляного вала вокруг ядра крепости.
По пути в Порт-Артур К.И. Величко некоторое время работал во Владивостоке. Обе эти крепости роднил не только театр военных действий, но и общая проблема достижения максимально возможной мощности при скудном финансировании и малой численности гарнизонов. Их объединил и общий руководитель проекта – ординарный профессор Николаевской инженерной академии полковник К.И. Величко. Выполняя директиву военного министра генерал-лейтенанта А.Н. Куропаткина, он значительно сократил линию обороны Владивостокской крепости и спроектировал ее в виде сплошной ограды. Итогом его работы во Владивостоке накануне Русско-японской войны становятся: три полудолговременных форта (форты Величко), три люнета, шесть опорных пунктов (форты Буйницкого). Помимо новых и реконструированных старых батарей, обустройства для их нужд новых дорог, строительства казарм для артиллеристов, морской фронт получил дополнительно пороховые погреба и целый пироксилиновый городок в бухте Диомид. «План обороны, который составили под руководством полковника К.И. Величко, не внес существенных корректив в проводимые работы по строительству береговых батарей, но после его утверждения в 1900 году работы на береговом фронте заметно ускорились».
В 1901 г. К.И. Величко было присвоено звание заслуженного ординарного профессора и воинское звание генерал-майора, а вскоре он был назначен помощником начальника Главного инженерного управления.