В 37 г. из Галлии вернулся Агриппа, которому и было поручено ведение военной кампании. Основной силой Помпея был огромный флот (350 кораблей), Агриппа начал масштабное строительство судов и набрал 20 тыс. гребцов из освобожденных на волю рабов. Для тренировки был устроен огромный полигон, созданный в результате соединения двух озер, Авернского и Лукринского (Flor., IV, 8, 6; Арр. B.C., V, 92, 95; Suet. Aug., 16; Veil., 79).
1 июля 36 г. Октавиан начал наступление. Предполагался тройной удар: с севера Сицилию атаковал Октавиан, которого прикрывал флот Агриппы, с юга, из Африки, наступал Лепид, из Тарента наносили удар корабли Антония под началом Статилия Тавра. Помпей оставил против Лепида один легион Плиния Руфа и сосредоточил главные силы армии и флота у Мессаны и Липар с целью отразить основного противника (Арр. B.C., V, 97–98). Подобный план показывает, что Помпей руководствовался не только военными, но и политическими соображениями, рассчитывая на разногласия между Октавианом и Лепидом.
Лепид высадил в Сицилии огромные силы, 12 легионов и 600 нумидийских стрелков, для обеспечения переправы было выделено 1 000 транспортов и 70 боевых кораблей. Опальный триумвир явно рассчитывал занять остров и вернуть прежние позиции во власти (Арр. B.C., V, 98–99; Dio., 49, 1). Высадка прошла успешно, Лепид занял Липары и осадил Лилибей.
Напротив, на севере наступление захлебнулось. Буря заставила флот Тавра отступить в Тарент, а Октавиан, продолжавший плавание, потерял 30 кораблей и множество либурн (Арр. B.C., V, 98–102; Dio., 49, 1; Veil., II, 79). Наступление вскоре возобновилось, на острове высадились войска Валерия Мессалы, а Агриппа атаковал у Мил эскадру Демохара (40 кораблей). На помощь подошла вторая эскадра Аполлофана (45 кораблей), а затем и сам Помпей с главными силами флота (70 кораблей). После ожесточенного морского сражения, победу одержал Агриппа, Помпей потерял 30 кораблей (Арр. B.C., V, 105–108; Dio., 49, 1–4; Veil., II, 79, 4; Liv. Epit., 129).
Успех при Милах позволил продолжить наступление на суше. С 3 легионами и 500 всадников Октавиан высадился у Тавромения. Помпей захлопнул кольцо, отрезав войска с моря. Октавиан чуть не погиб и с остатками флота с трудом добрался до италийского побережья. Командование армией было передано Л. Корнифицию, который с трудом добрался до Тиндариды. Образовавшийся плацдарм был прикрыт флотом Агриппы (Арр. B.C., V, 111–115; Dio., 49, 4-7; Veil, II, 79, 4; Suet. Aug, 16).
Октавиан наращивал силы под прикрытием флота. Вскоре его армия в Сицилии выросла до 7 легионов, 14 было у Лепида. Армия Лепида двигалась к Мессане, а 10 легионов Помпея заняли оборону на небольшом пятачке в районе Мессаны, Мил, Тиндариды и Навлоха (Арр. B.C., V, 116–117). Теперь Агриппа мог нанести решающий удар. 3 сентября 36 г. при Навлохе состоялось генеральное сражение между флотами Агриппы и Помпея. Согласно Аппиану, обе стороны имели по 300 кораблей, но современные ученые полагают, что у Помпея было не более 200. Помпей был разгромлен, у него осталось всего 17 судов (Dio, 49, 8–10; Арр. B.C., V, 118–121; Veil, И, 79, 5; Liv. Epit, 131).
Война закончилась. Помпей оставил Сицилию, а окруженные легионы Плиния Руфа сдались Лепиду (Арр. B.C., V, 122; Dio, 49, 2). Помпей бежал в Малую Азии, пытался добиться поддержки Антония, но затем поднял мятеж, был захвачен в плен и казнен по приказу Антония (Арр. B.C., V, 133–140; Dio, 49, 17–18; Veil, II, 79, 5; Liv. Epit, 131).
Теперь произошло столкновение между Октавианом и Лепидом. После присоединения Плиния Руфа, у Лепида было 22 легиона. Он запретил городам Сицилии принимать гарнизоны Октавиана и потребовал передачи ему острова и возвращения статуса триумвира. Свое слово снова сказали солдаты, Октавиан прибыл в лагерь Лепида с небольшой свитой, армия перешла на его сторону, и теперь уже Лепид униженно молил о пощаде. Ему сохранили жизнь и сан великого понтифика и консуляра, однако оставшуюся жизнь (до 12 г. до н.э.) Лепид прожил на положении опального вельможи (Liv. Epit, 129; Suet. Aug, 16; Dio, 49, 11–12, 14; Veil, II, 80).
Сицилийская война создала новую политическую ситуацию. Остатки республиканцев и помпеянцев окончательно прекратили сопротивление. Большинство высокопоставленных проскриптов и бывших сторонников Брута и Кассия уже покинули Помпея, другие сдались. Большинство простых солдат были зачислены в армию Октавиана. Гораздо более жестоким образом поступили с рабами: 30 000 пленных рабов были возвращены хозяевам, несколько тысяч, чьи хозяева не нашлись или погибли, были казнены (Арр. В. С, V, 131; Dio, 49, 12). Пропаганда Октавиана объявила войну акцией против беглых рабов и пиратов, фактически идентифицировав ее с антипиратской операцией Гнея Помпея в 67 г. (R.g, 25).