Несмотря на то, что время начала десантной операции было оптимальным, погода и в этот раз немного помогла Помпею. И эскадру Марка Лепида, и эскадры Октавиана изрядно потрепала буря. У Октавиана одна эскадра вынуждена была вернуться в Тарент, а в другой во время бури погибло 6 тяжелых судов, 26 более легких судов и до трех десятков легких галер-либурнов. Однако и эпидемия и буря могли теперь лишь задержать Октавиана, но не остановить. Моряков, спасшихся со своих затонувших кораблей, Октавиан направил для пополнения поредевших экипажей кораблей Антония, а пригодные к ремонту суда приказал срочно ремонтировать. Хотя на приведение в порядок оставшихся судов ушло более месяца, к концу лета флот Октавиана вновь был в полной готовности про-, должать войну.
Марк Лепид во время бури потерял много транспортных судов, но все же сумел высадить в Сицилии своих 12 легионов, 5 тысяч нумидийских всадников и необходимое снаряжение. С этой огромной армией Лепид осадил крепость Лилибей на западном побережье Сицилии. Для защиты Лилибея Помпей смог выделить только один тяжеловооруженный легион и крупный отряд легковооруженных воинов, поручив защиту крепости своему полководцу Плинию.
Некоторые соседние города Сицилии без боя подчинились Лепиду, но в целом завоевание Сицилии продвигалось медленно. У Помпея все еще было немало сторонников, и постепенно ему удалось довести численность войск Плиния до восьми легионов. Октавиан сумел переправить в Сицилию для взаимодействия с Лепидом небольшую армию во главе с Мессалой, но переправка основной части войск задерживалась.Помпей всячески препятствовал переправе. Основные силы его флота были сконцентрированы у Мессенского пролива, но отдельные эскадры действовали вдоль всего побережья. Одна из таких эскадр сумела перехватить большой караван судов Лепида, везших ему подкрепление. Часть судов прорвалась, но в море погибло два легиона. Еще больше Помпею повезло в августе 36 года. Октавиан со всем своим флотом выдвинулся к Липарским островам (к северу от Сицилии), пытаясь изучить возможности высадки своих войск к северу от Мессины, а затем, передав командование Агриппе, с небольшой частью флота решил захватить город Тавромений к югу от Мессины, чтобы ударить по Помпею с двух сторон. Агриппа же захватил несколько островов, а затем вступил при Милах в сражение с флотоводцем Помпея Папием,
незадолго до того разгромившим караван судов, шедших к Лепиду. Имевший более мощные суда Агриппа, потеряв всего 5 своих кораблей, сумел потопить 30 кораблей противника, в том числе и флагманский корабль Папия, но тому удалось спастись на другом корабле и увести остальные корабли. Многие корабли Агриппы были серьезно повреждены и нуждались в ремонте, а кроме того, Папий отошел на мелководье, и Агриппа решил не пытаться преследовать противника, дав ему укрыться в гавани. После этого Агриппа осадил город Тиндариду, а Октавиану отправил сообщение о своей победе.Октавиан сначала хотел подплыть к Тавромению и высадить войска ночью, но, узнав о победе Агриппы, решил плыть днем. Подведя свою эскадру к городу, Октавиан принялся склонять его защитников к сдаче, а когда гарнизон отказался, стал выгружать свои войска у города, разбивая лагерь. В это время с моря появился флот Помпея, с берега же подошла его конница, а затем и пехота. Всадники Помпея начали беспокоить легионеров Октавиана, занятых сооружением лагеря. У Октавиана имелось три легиона пехоты, 500 всадников без лошадей, тысяча легковооруженных воинов и две тысячи ветеранов-добровольцев, однако это было меньше, чем те силы, что привел Помпей, и войска охватил страх. Если бы Помпей имел больший опыт сухопутных сражений, то, воспользовавшись внезапностью, мог бы одновременным ударом с суши и моря разгромить растерявшиеся войска Октавиана и захватить того в плен. Но Помпей не знал о настроении вражеских войск и не решился начать битву в вечернее время, что позволило солдатам Октавиана укрепиться.
Утром Октавиан поручил командование десантом Корнифицию
(не следует путать этого Корнифиция с Корнифицием — наместником Африки, боровшимся против триумвиров и погибшим в 43 году до нашей эры). Правое крыло он поручил Титинию, левое — Каризию, а сам, взойдя на либурнское судно, объезжал свои корабли и подбадривал воинов.Помпей атаковал эскадру Октавиана. Первую атаку Помпея удалось отбить, но через некоторое время он атаковал снова и в длившемся до самой ночи сражении сумел захватить или сжечь большинство судов Октавиана. Сам Октавиан ночью с большим трудом сумел прорваться к материку и вынужден был сойти на берег и спасаться бегством с одним лишь оруженосцем. Возможно, именно тогда произошел случай, о котором упоминает Светоний Транквилл, говоря, что «когда после этого он спасался бегством по узким тропинкам, то раб его спутника Эмилия Павла попытался его убить, воспользовавшись удобным случаем, чтобы отомстить за Павла-отца, казненного во время проскрипций».