На переходе морем командующий эскадрой Л. Гейден, присмотревшись к расторопному гардемарину, назначил Владимира Истомина своим порученцем.
Во время Наваринского сражения флагманский корабль «Азов» принял на себя основной огневой шквал египетско-турецкой эскадры.
Отражая атаки пяти вражеских кораблей, ответный орудийный шквал «Азова» вскоре вывел из строя флагманов неприятеля. «Все русские корабли отважно сражались против превосходящих сил противника, — в тот же день доносил флагман. — Капитаны и прочие офицеры российской эскадры исполняли долг свой с примерным рвением, мужеством и презрением всех опасностей; нижние чины отличались храбростью и повиновением, которые достойны подражания.
Неустрашимый капитан первого ранга М. Лазарев... управляя движениями «Азова» с хладнокровием, искусством и мужеством примерным; капитаны Авинов, Хрущев, Богданович и Свинкин равно отличились. Сей последний, хотя при начале дела был тяжело ранен картечью, но продолжал командовать во всё сражение, держась около четырёх часов за канат и на коленях на палубе своего корабля. Капитан «Гангута» Авинов явил также пример редкого присутствия духа; турецкий фрегат, обращённый в брандер, пробрался между сим кораблём и адмиральским бугшпритом, уже сцепился с «Гангутом», капитан Авинов велел брать сей фрегат на абордаж, и человек, готовившийся оный зажечь, убит с фитилём в руках.
Один из турецких фрегатов, сражавшихся против корабля «Александр Невский», сдался и спустил флаг, который взят; турки на другой день отправлены на берег, а фрегат потонул»..
Контр-адмирал Гейден под огнём неприятеля умело руководил действиями кораблей русской эскадры. Ему помогал и юный порученец Владимир Истомин, получивший боевое крещение в этом сражении. Наградой ему был серебряный крест Святого Георгия.
Среди отличившихся в Наваринском сражении Гейден отметил и своих помощников — «должность исполняли с необыкновенным усердием и деятельностью, а особенно Истомин, коего не могу довольно нахвалиться ».
Спустя десять дней Гейден, превышая свои полномочия, произвёл Истомина и его товарищей в мичманы — первый офицерский чин, о чём доносил Меншикову: «Во уважение отличной их храбрости и деятельности во время сражения».
Два года мичман Истомин во время войны с Турцией на «Азове» крейсирует в Средиземном море, участвует в блокаде Дарданелл и затем возвращается с эскадрой М. Лазарева в Кронштадт.
Представляя список офицеров, достойных награды, Лазарев характеризует 19-летнего мичмана В. Истомина: «Весьма исправен и в должности ревностный и деятельный офицер». Адмирал упоминает Истомина среди «тех офицеров, которые в продолжении времени соделались, так сказать, украшением нашего флота».
Последующие две кампании В. Истомин крейсирует на Балтике в составе эскадры на фрегате «Мария» и корабле «Память Азова».
В 1833 году он произведён в лейтенанты, а кампанию 1836 года начал на Черноморском флоте в составе экипажа 120-пушечного линейного корабля «Варшава».
Эскадра, в составе которой крейсировала и «Варшава», была в готовности принять десант для высадки в Босфоре. В это время в связи с обострением отношений с Францией и Англией не исключалась вероятность появления в Черном море англо-французской эскадры. Следующую кампанию лейтенант Истомин встречает командиром 10-пушечной яхты «Резвая», а затем назначается командиром одного из первых на Черном море парохода «Северная звезда».
В 1837 году на берега Чёрного моря пожаловал император Николай I с супругой, императрицей Александрой Фёдоровной. Царствующие особы совершали прогулку вдоль берегов Чёрного моря на военном пароходе «Северная звезда». Для её командира пребывание на борту императора закончилось благополучно. В. Истомина наградили орденом Святого Владимира IV степени, а «их величества» пожаловали его двумя бриллиантовыми перстнями.
Недавно построенная на верфях Николаева 16-пушечная шхуна «Ласточка» предназначалась в кампанию 1838 года в Абхазскую экспедицию для крейсерства у берегов Кавказа, но поступило указание Морского штаба срочно отправить её в Афины в распоряжение русского посланника. Зарекомендовавший себя прекрасным моряком командир шхуны лейтенант В. Истомин, как никто другой, знал акваторию Архипелага и Средиземного моря. Посланник России в Афинах Гавриил Катакази был весьма доволен прибытием «Ласточки». Вскоре все капитаны английских и французских судов в Архипелаге восхищались образцовым состоянием «Ласточки» и отличной выучкой её экипажа во главе с её капитаном В. Истоминым. Одним из первых «Ласточку» посетил английский посланник, капитан флота её величества Эдмунд Лайонс. Англичанин давно питал особый интерес не только к русским военным судам, но и их колыбели, — Севастополю. По заданию своего Адмиралтейства в прошлом он не раз на шхунах, крадучись, пробирался в Севастополь, но в последнее время, с появлением там Лазарева, это стало невозможным. Знал и В. Истомин о визитах в Чёрное море английского лазутчика, но при общении с Лайонсом вида не подавал.
В чём был откровенно искренним англичанин, так это в оценке «Ласточки».
— Я нахожу вашу шхуну и матросов в прекрасном виде, — сказал он Истомину при первом же визите.
Истомин пригласил Лайонса в каюту, и за вполне дружеским застольем оба моряка нашли общий язык, несмотря на разницу в возрасте: Лайонс был старше Истомина на двадцать лет.
Прощаясь, английский капитан пригласил Истомина в гости, и с тех пор, пока «Ласточка» находилась в Афинах, они постоянно общались.
За время пребывания в Средиземном море, В. Истомин не раз бывал со шхуной на Мальте, в Адриатике, избороздил греческий Архипелаг.
Зимой 1840 года «Ласточка» возвратилась в Севастополь, и вскоре её экипаж включился в подготовку к очередной десантной операции на Кавказ. Уже в марте 1840 года «Ласточка» в составе эскадры контр-адмирала Станюковича, погрузив часть десанта, отправилась в Феодосию. В десантной операции у Туапсе шхуне «Ласточка» предписывалось действовать на левом фланге десанта. Участвовал в высадке десанта 20 мая и брат В. Истомина, адъютант Лазарева, Гвардейского экипажа капитан-лейтенант Константин Истомин. Десантная операция прошла успешно, на берег было высажено 9000 человек с артиллерией, боезапасами, провизией.
На шхуне «Ласточка» износились паруса, и её отправили в Николаев обновить снаряжение.
Лазарев, скупой на похвалу, по достоинству оценил службу В. Истомина, вскоре посылает рапорт Меншикову о повышении в должности и звании.
«Лейтенанта В. Истомина, в. с-ть непременно произвели бы сами, если бы увидели возвращение в зимнее время шхуну «Ласточку»; описываемые мне в партикулярном письме Катакази отзывы о ней англичан и французов, командовавших военными судами в Архипелаге, и в особенности флота капитана Лайонса, возвышают честь российского флота за границей... Истомин восьмой год как служит лейтенантом и 13 лет — офицером, я намерен представить в. св-ти о назначении его командиром на имеющей заложиться послезавтра корвет и в таком случае чин капитана-лейтенанта очень соответствовал бы таковому командованию. Познания его и заботливость по службе доставят флоту отличнейший корвет».
В июле 1840 года Истомин произведён в капитан-лейтенанты и назначен командиром корвета «Андромаха».
Две кампании «Андромаха» с перерывами на ремонт и отдых экипажам крейсировала в Абхазской экспедиции у берегов Кавказа. Турецкие контрабандисты в эту пору присмирели, не решались действовать в открытую, использовали непогоду и тёмными ночами под берегом иногда ускользали от дозоров. Вовсе прекратили свои визиты английские лазутчики, так как Лазарев решительно пленил их суда без оглядки на Петербург. Другое дело, что на побережье горцы продолжали частыми набегами на укрепления наносить иногда значительный урон войскам. Тогда армейские начальники обращались за помощью к морякам.
В 1844 году корабли флота для усиления армии на Кавказе переправили через Керченский пролив пехотную дивизию. С приходом нового командующего, наместника на Кавказе, генерала Воронцова, действия против горцев активизировались. Для налаживания более тесного взаимодействия с войсками Лазарев назначил В. Истомина своим представителем при ставке наместника:
