Агриппа неутомимо тренировал недавно скомплектованные экипажи своих кораблей; многие из гребцов и матросов на них были рабы, совсем недавно впервые познакомившиеся с корабельным делом. А ведь им противостояли пиратские экипажи Помпея, привычные к морю и морским сражениям. Агриппе и с этим трудным делом удалось справиться.
Весной 36 года до н. э. новый флот Октавиана был готов к действию. Он вышел в море, чтобы переправить у Мессаны армию в Сицилию и разбить флот Секста Помпея. У мыса Полинура корабли попали в сильную бурю, многие их них были серьезно повреждены, и Агриппа возвратился в порт Юлия для их ремонта. Та же буря повредила 70 кораблей, высланных членом второго триумвирата Лепидом из Африки на помощь Октавиану, а 120 кораблей, посланных Марком Антонием для той же цели из Египта, вынуждены были искать укрытия в портах Греции.
Как только ремонт кораблей в порту Юлия был завершен, Агриппа направился к Липарским островам, занял самый южный из них (Термесса или Гиера) и использовал его для наблюдения за неприятельским флотом, стоявшим в Миле, напротив этого острова в 12–15 милях. Помпеянским флотом командовал вольноотпущенник Демохар, а сам Секс Помпей стоял с эскадрой у Мессаны, чтобы помешать переправе Октавиана с войсками в Сицилию.
Наконец Агриппа атаковал помпеянский флот. В бою сказалось то, что корабли помпеянцев вследствие более легкой конструкции были менее устойчивы против таранных ударов, а также ввиду меньшей численности экипажей и меньшей высоты бортов проигрывали и в абордажных боях. Агриппе удалось пустить ко дну неприятельский флагман. Демохар вплавь с экипажем перебрался на другой корабль. Агриппа потерял 5 кораблей, а помпеянцы 30, и вынуждены были отступить, хотя и сделали это в полном порядке.
Октавиан высадил десант у Тавромения, но на обратном пути был атакован эскадрой Помпея и разбит. Все его корабли были потоплены или сожжены, а остальные захвачены помпеянцами. Сам Октавиан едва спасся на шлюпке. Десант у Тавромения был сильно потрепан войсками Секста Помпея. Только высаженный Агриппой отряд сумел восстановить положение и помог удержать плацдарм для высадки остальных войск Октавиана.
Решительная битва произошла 3 сентября 36 года до н. э. при Навлохе. Агриппа имел 420 кораблей, а флотилия Секста Помпея под командой вольноотпущенников Демохара и Аполлофана насчитывала 180 кораблей. Флот помпеянцев шел с востока, эскадра Агриппы – с запада. Обе эскадры были развернуты фронтом и, судя по большому числу кораблей, участвовавших в битве, вероятнее всего, поставлены в две линии. Рано утром эскадры устремились навстречу друг другу. Сперва заработали метательные машины, затем на близкой дистанции вступили в бой пращники и лучники, полетели копья и горящие дротики. Противники старались таранить друг друга, обламывать весла или брать неприятельские корабли на абордаж.
