Образование получил в Морском кадетском корпусе, куда поступил 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-й степени. В это же время им были составлены временное положение об обязонностях чинов штаба командующего Черноморским флотом и ряд инструкций, сохранивших силу и по окончании войны.
