Две кампании «Андромаха» с перерывами на ремонт и отдых экипажам крейсировала в Абхазской экспедиции у берегов Кавказа. Турецкие контрабандисты в эту пору присмирели, не решались действовать в открытую, использовали непогоду и тёмными ночами под берегом иногда ускользали от дозоров. Вовсе прекратили свои визиты английские лазутчики, так как Лазарев решительно пленил их суда без оглядки на Петербург. Другое дело, что на побережье горцы продолжали частыми набегами на укрепления наносить иногда значительный урон войскам. Тогда армейские начальники обращались за помощью к морякам.
В 1844 году корабли флота для усиления армии на Кавказе переправили через Керченский пролив пехотную дивизию. С приходом нового командующего, наместника на Кавказе, генерала Воронцова, действия против горцев активизировались. Для налаживания более тесного взаимодействия с войсками Лазарев назначил В. Истомина своим представителем при ставке наместника:
— Поимейте в виду, Владимир Иванович, — наставлял Лазарев перед убытием Истомина, — Воронцов вояка стрелянный со времён Наполеона. Потому Старайтесь лицом в грязь не ударить. Впрочем, вы дипломатии в Греции обучились.
Три с лишним года провёл Истомин в ставке Воронцова. Приходилось ему не только обеспечивать взаимодействие войск на Кавказском побережье, но и сопровождать Воронцова на Каспий, где он начал операцию против Шамиля. Но связи с флотом Истомин не порывал, о чём свидетельствует его переписка с Лазаревым.
Лазарев благодарит Истомина за сведения о Каспийском театре, старается подбадривать его в борьбе с местными казнокрадами:
Лазарев сообщал Истомину о всех важных событиях флотской жизни, о строительстве офицерского собрания, о восстановлении Морской библиотеки. Не забывает и о дружбе Истомина с Нахимовым. «Кагул» назначен в Абхазский отряд, и на нем пойдёт П.С. Нахимов. Может быть, вы там его увидите».
Истомин ещё не знает, что Лазарев уже прочит ему командовать «Парижем», а пока он участвует в схватках Кавказской войны...