На переходе морем командующий эскадрой Л. Гейден, присмотревшись к расторопному гардемарину, назначил Владимира Истомина своим порученцем.
Во время Наваринского сражения флагманский корабль «Азов» принял на себя основной огневой шквал египетско-турецкой эскадры.
Контр-адмирал Гейден под огнём неприятеля умело руководил действиями кораблей русской эскадры. Ему помогал и юный порученец Владимир Истомин, получивший боевое крещение в этом сражении. Наградой ему был серебряный крест Святого Георгия.
Среди отличившихся в Наваринском сражении Гейден отметил и своих помощников — «должность исполняли с необыкновенным усердием и деятельностью, а особенно Истомин, коего не могу довольно нахвалиться ».
Спустя десять дней Гейден, превышая свои полномочия, произвёл Истомина и его товарищей в мичманы — первый офицерский чин, о чём доносил Меншикову: «Во уважение отличной их храбрости и деятельности во время сражения».
Два года мичман Истомин во время войны с Турцией на «Азове» крейсирует в Средиземном море, участвует в блокаде Дарданелл и затем возвращается с эскадрой М. Лазарева в Кронштадт.
Представляя список офицеров, достойных награды, Лазарев характеризует 19-летнего мичмана В. Истомина: «Весьма исправен и в должности ревностный и деятельный офицер». Адмирал упоминает Истомина среди «тех офицеров, которые в продолжении времени соделались, так сказать, украшением нашего флота».
Последующие две кампании В. Истомин крейсирует на Балтике в составе эскадры на фрегате «Мария» и корабле «Память Азова».
В 1833 году он произведён в лейтенанты, а кампанию 1836 года начал на Черноморском флоте в составе экипажа 120-пушечного линейного корабля «Варшава».
Эскадра, в составе которой крейсировала и «Варшава», была в готовности принять десант для высадки в Босфоре. В это время в связи с обострением отношений с Францией и Англией не исключалась вероятность появления в Черном море англо-французской эскадры. Следующую кампанию лейтенант Истомин встречает командиром 10-пушечной яхты «Резвая», а затем назначается командиром одного из первых на Черном море парохода «Северная звезда».