Образование получил в Морском кадетском корпусе, куда поступил 9 августа 1799 года, 17 апреля 1807 года Мелихов был произведён в гардемарины и на фрегате «Спешный» под командованием капитан-лейтенанта Н. Г. Ховрина отправлен в Средиземное море. Когда фрегат стоял в Портсмуте, между Россией и Англией началась война, и «Спешный» был взят в плен. В январе 1808 году Мелихов вместе с другими гардемаринами был освобождён и через Швецию вернулся в Россию. В том же году он состоял на корабле «Орёл» под командованием капитана 1-го ранга О. Е. Гастфера и на фрегате «Малый» под командованием капитан-лейтенанта Ф. И. де Ливрона и принимал участие в делах против шведов. 24 декабря 1809 года был произведён в мичманы и назначен на тендер «Снапоп». 31 марта 1810 года он был переведен в 3-й гребной экипаж и весной-осенью находился на Кронштадтском рейде на гемаме «Петергоф» под командованием лейтенанта И. Б. Гаврино.
Переведённый 27 февраля 1811 года в Черноморский флот, он летом того же года на ковете «Ягудиил» под командованием капитан-лейтенанта Ф. Ф. фон Беллинсгаузена плавал у берегов Болгарии для блокады побережья. В декабре он встретил неудачу: бриг «Царь Константин» под командованием капитан-лейтенанта Г. М. Костенича, на который Мелихов был назначен, потерпел крушение у Анапского мыса, и экипаж его вынужден был провести четыре зимних месяца в полуразрушенной крепости, терпя вместе с гарнизоном её всякие лишения и наскоки горцев. После возвращения в Севастополь он состоял на корвете «Евлампий» под командой своего прежнего командира и вновь находился в блокаде турецких берегов на фрегате «Лилия» под командованием капитан-лейтенанта И. В. Винклера, на корабле «Двенадцать Апостолов» под командованием капитан-командора К. Ю. Патаниоти и на транспорте «Рион» под командованием капитан-лейтенанта И. С. Скаловского. 26 июля 1814 года Мелихов был произведён в лейтенанты и назначен в Херсон на строительство корабля «Париж», на котором в следующем году плавал от Херсона до Очакова и Севастополя под командованием капитан-лейтенанта И. И. Стожевского. 12 июня 1816 года он был переведен в 33-й флотский экипаж и в компанию находился в крейсерстве по Черному морю на корабле «Лесной» под командованием капитана 1-го ранга М. С. Микрюкова и на фрегате «Лилия» под командованием капитан-лейтенанта И. В. Винклера
В 1817 году назначен флаг-офицером к вице-адмиралу Грейгу, который скоро оценил его административные способности. 1 марта 1822 года он был награжден орденом Св. Владимира 4-й степени с бантом, а 22 декабря 1823 года получил чин капитан-лейтенанта. Состоя в должности начальника штаба главного командиpa Черноморского флота (в 1826—1830 годах), Мелихов составил проект офицерской библиотеки в Севастополе, тогда же проведённый в жизнь.
Во время войны с Турцией 1828—1829 годов за участие в покорении Анапы и взятие в плен четырёх турецких судов при осаде Варны под выстрелами крепости Мелихов получил два чина — капитана 2-го ранга (9 июля) и капитана 1-го ранга (18 августа) и орден Св. Владимира 3-й степени. В это же время им были составлены временное положение об обязонностях чинов штаба командующего Черноморским флотом и ряд инструкций, сохранивших силу и по окончании войны.
Из-за разногласий с адмиралом Грейгом Мелихову пришлось уйти из Черноморского флота, но 25 марта 1830 года, со вступлением в должность начальника морского штаба князя Меншикова, Мелихов был назначен состоять при нём для особых поручений, а 17 декабря того же года назначен вице-директором Инспекторского департамента Морского министерства. В том же году он составил перечень командных слов для внутренней службы на корабле и новую систему сигналопроизводства, значительно ускорившую подъём и разбор сигналов.
Независимо от своих прямых обязанностей в 1831 году Мелихов состоял членом комитета по устройству карантинной стражи и в 1831—1837 годах — членом комитета образования флота. Произведённый 10 апреля 1832 года в контр-адмиралы Мелихов 8 ноября того же года был назначен членом Адмиралтейств-совета, откуда 11 апреля 1836 года перемещён в члены морского генерал-аудиториата. 6 апреля 1835 года Мелихов был награжден орденом Св. Станислава 1 степени, 1 декабря того же года орденом Св. Георгия 4-й степени, 6 декабря 1840 года получил чин вице-адмирала.
Во флоте в это время, за неимением современного морского устава, продолжали руководствоваться устаревшими регламентами Петра I, что вызывало множество недоразумений, способствовало произволу начальников и подрывало воинскую дисциплину. По собственному почину Мелихов взял на себя капитальный труд составления свода морских уголовных постановлений, над которыми проработал 14 лет. По составлении этого свода Мелихов приступил к разработке нового морского устава, в котором проекты девяти наиболее существенных глав были составлены им лично.
Назначенный 19 апреля 1853 года председателем морского аудиториата, Мелихов по поручению великого князя Константина Николаевича занялся систематизацией счётной части морского министерства. 17 апреля того же года он был награжден Св. Владимира 2-й степени.
С началом Восточной войны Мелихову было поручено наблюдение за постройкой 64 канонерских лодок, заказанных казённым адмиралтействам и нескольким частным верфям. За блестящее выполнение этого поручения (все лодки были готовы через 2 месяца) Мелихов 6 декабря 1854 года был произведён в адмиралы и 31 декабря назначен членом Государственного совета. В начале 1856 года Мелихов по поручению великого князя Константина Николаевича совершил командировку в Николаев, где произвёл ревизию смет Черноморского флота.
Среди прочих наград Мелихов имел ордена:
Скончался Мелихов 30 ноября 1863 года в Санкт-Петербурге, похоронен на Тихвинском кладбище Александро-Невской лавры.
После себя Мелихов оставил сочинение «Описание действий Черноморского флота в продолжение войны с Турцией в 1828 и 1829 годах» (СПб., 1850).
Мелихов был женат на дочери известного благотворителя коллежского асессора К. В. Злобина Ольге Константиновне, у них было двое детей: сын Константин умер в младенчестве и дочь Елена (1838 — после 1861).