Опытнейший моряк Лазарев быстро понял, что из избалованного столичной жизнью молодого мичмана может выйти прекрасный офицер, и обходился с ним особенно пристрастно, что воспринималось Корниловым как необоснованные придирки. Однажды Лазарев прямо спросил Корнилова, желает ли он продолжать службу на флоте. Получив утвердительный ответ, Михаил Петрович высказал ему свой взгляд на обязанности морского офицера, а затем, по словам самого Корнилова, любившего рассказывать об этом эпизоде, самолично выбросил за борт все книги молодого офицера, составлявшие в основном фривольные французские романы, и заменил их книгами по морскому делу из своей собственной библиотеки.

М. П. Лазарев не ошибся. Место петербургского повесы занял серьезный, ответственный морской офицер. В наваринском сражении мичман Корнилов, командуя тремя орудиями нижнего дека, по словам Лазарева, «был одним из самых деятельных, расторопных и исполнительных офицеров», за что был награжден орденом Св. Анны 4-й ст., французским орденом Св. Людовика, английским орденом Бани и греческим орденом Св. Спасителя. В 1828 г. Корнилов был произведен в лейтенанты.

После завершения военных действий в Средиземноморье Корнилов вернулся служить на Балтику, но затем Лазарев, ставший начальником штаба Черноморского флота, вызвал запомнившегося ему офицера в Севастополь. В 1833 г. Россия, вмешавшись в урегулирование египетско-турецких отношений, сумела навязать Османской империи выгодный для себя Ункиар-Искелессийский договор. В связи с этим была организована Босфорская экспедиция, в которой лейтенант Корнилов на корабле «Память Евстафия» выполнял поручение Лазарева по военно-географическому обследованию района Босфора и отлично с ним справился. По окончании миссии он был награжден орденом Святого Владимира 4-й степени и турецким золотым знаком отличия.

Служба Корнилова шла своим чередом. Он командовал бригом «Фемистокл», корветом «Орест», фрегатом «Флора». 1 января 1838 г. Корнилов был назначен командиром строящегося линейного корабля «Двенадцать Апостолов». По заведенному Лазаревым порядку командир корабля обязан был лично следить за его строительством. По инициативе Корнилова корабль «Двенадцать Апостолов» впервые в русском флоте был вооружен новым оружием — 68-фунтовыми бомбическими орудиями. Корнилов разработал и издал ряд приказов, распоряжений и инструкций, касающихся всех сторон организации службы на корабле. Лазарев дал высокую оценку экипажу корабля «Двенадцать Апостолов», а разработанный Корниловым распорядок службы был введен Лазаревым на всех кораблях Черноморского флота:

«Решительно можно сказать, что другой подобный корабль едва ли в каком другом флоте есть».

В 1846 г. Корнилов был командирован в Англию, где изучал состояние ВМС, а также наблюдал за строительством новых паровых кораблей для Черноморского флота, а с 1849 г. стал исполнять обязанности начальника штаба эскадры Лазарева, принимая участие в строительстве кораблей, выходя в плавания, готовя планы действия эскадры и разрабатывая задачи для каждого корабля.

Корнилов придерживался передовых взглядов на развитие военно-морских сил, выступал за скорейшую замену парусных кораблей паровыми, за внедрение новой артиллерии, написал ряд руководств и наставлений, участвовал в разработке нового Морского устава. После смерти Лазарева в руках Корнилова сосредоточилась фактически вся власть в управлении Черноморским флотом. В 1852 г. Владимир Алексеевич был произведен в вице-адмиралы и получил звание генерал-адъютанта. Ожидая дальнейшего обострения обстановки на южных рубежах России, он предпринимал энергичные меры по строительству новых судов в Николаеве, расширению доков и адмиралтейства в Севастополе, пополнению артиллерийских арсеналов. Но времени, чтобы укрепить крымские берега, ему не хватило — события развивались слишком быстро. «Спор о палестинских святынях» стремительно перерастал в войну. После неблагоприятного результата миссии А. С. Меншикова в Константинополе, в которой принимал участие и Корнилов, война России с англо-франко-турецкой коалицией стала неизбежной. События в Синопе ускорили развязку.