И действительно, Октавиан скоро восстановил свои силы. Большой флот под командованием Агриппы двинулся к северному побережью Сицилии. Флот Тавра высадился на восточном побережье острова вблизи города Тавромения. Октавиан и Тавр хотели сделать из Тавромения свою базу для действий в этом районе, но его жители отказались сдаться, так что высадившимся пришлось устраивать лагерь недалеко от города. Там временем Агриппа, овладев островом Гиерой, двинулся к городу Милы, где находилась часть помпеянского флота под командованием Демарха. Помпей направил на помощь Демарху другую эскадру, которой командовал Аполлофан. И в первой половине августа 36 г. до н. э. около Мил произошло ожесточенное морское сражение. В целом перевес оказался на стороне Агриппы. Помпеянские корабли отступали в порядке; они были более легкими и верткими, а их матросы хорошо знали окрестное побережье, так что преследовать их корабли Агриппы не смогли. Однако исход этого сражения привел к тому, что силы Помпея не смогли помешать переправиться на остров сухопутным войскам Октавиана, что сделало положение Секста довольно тяжелым.

Считая, что главная опасность грозит ему с восточного побережья, где со своими войсками находился Октавиан, Помпей двинулся к Тавромению. Там произошел бой, который закончился в пользу Помпея, но из-за наступающего вечера Секст отложил штурм лагеря Октавиана, а на следующий день он увидел, что лагерь оказался сильно укрепленным, и отступил. Положение Октавиана все равно оставалось трудным. Он вызвал себе помощь из Италии, а пока часть своей армии во главе с Корнифицием направил в глубь Сицилии на соединение с Агриппой, который к этому времени овладел территорией на северном берегу острова. С большим трудом Корнифицию удалось соединиться с Агриппой, что весьма усилило находившиеся в этом районе войска Октавиана. Помпей пытался было помешать движению войск врага, заняв проходы в горах между Тавромением и Мессиной, но Октавиан сумел преодолеть это препятствие, и Помпей отступил к Мессине. Октавиан направил Тавра, чтобы тот отрезал лагерь Секста от подвоза продовольствия. И Помпей решил действовать более активно. Возлагая свои основные надежды на флот, он решил вынудить противника вступить в морское сражение.

3 сентября 36 г. до н. э. на широте якорной стоянки Навлоха между Милами и Мессиной произошло решающее сражение. Бой был очень ожесточенным, корабли сталкивались друг с другом, а воины часто переходили на палубы вражеских судов, схватываясь с противником врукопашную. И все же успех был на стороне Агриппы. Помпей потерял большую часть своего флота и в растерянности бежал в Мессину. Сухопутная армия Помпея, оставшаяся без полководца, сдалась Агриппе. Помпей потерял голову. Он вызвал из Лилибея находившиеся там части под командованием Плиния Руфа, но не дождался их. С еще оставшимися у него 17 кораблями Секст покинул Мессину и направился на восток. Занявший Мессину Руф через некоторое время капитулировал.

Помпей прекрасно понимал истинную цену дружбы между Антонием и Октавианом и хорошо знал, что рано или поздно они сойдутся в решительной схватке за верховную власть. И он решил подтолкнуть Антония к этой схватке и стать ему в ней союзником. Для начала Секст прибыл в Митилену, где всегда были сильны пропомпеянские настроения и где он сам вместе со своей мачехой жил в начале гражданской войны. Митиленцы благожелательно встретили сына Помпея Великого. Но в это время Секст узнал о поражении Антония от парфян и решил сыграть свою игру. Он одновременно направил своих послов и к Антонию в Александрию, и к царям Фракии и Понта, и в Парфию. Антония он призывал начать войну с Октавианом и обещал ему всяческую помощь. От фракийцев он ожидал защиты от нападения с Балканского полуострова. Через Понт намеревался добраться до Парфии. А от парфян ждал помощи в подготавливаемой войне, которую он собирался вести с Октавианом, но уже не ради дела Антония, а только в свою собственную пользу. При этом он рассчитывал, что благодарная память об его отце все еще живет в восточных провинциях республики и в местных вассальных царствах, так что он будет иметь в этом регионе солидную опору.

Однако планы Секста провалились. Отправленные им посольства к «варварам» были перехвачены агентами Антония, что дало тому повод начать подготовку к войне с Секстом. Главной причиной этого было, конечно, нежелание Антония иметь на своей территории ни в каком качестве, даже в качестве союзника, потенциально весьма опасного соперника. И Антоний приказал Марку Тицию собрать корабли и войско и двинуться против Помпея. Когда-то Тиций был захвачен моряками Секста, но тот отпустил его к Антонию, и теперь этот же Тиций стал командующим в возможной войне с Секстом Помпеем. А пока Секст сам собирал корабли и войско, антониевский наместник провинции Азии Гай Фурний, еще не зная о намерениях своего вождя, колебался и не решался открыто выступить против Помпея. Но тот скоро сам дал повод для такого выступления. Переправившись на материк, он захватил город Лампсак и из живших там колонистов Цезаря набрал три легиона пехотинцев и 200 всадников. Это стало сигналом к началу военных действий. В первом сражении Секст одержал победу, но к Фурнию скоро подошли подкрепления, и он снова выступил против Помпея. Военные действия развернулись на территории Вифинии. Помпей захватил города Никею и Никомедию, завладев там значительной добычей, но вскоре понял, что шансов успешно воевать с Антонием у него практически нет. Это поняли и некоторые из еще остававшихся с ним друзей, которые вместе с ним покинули Сицилию, а теперь решили все же оставить безнадежное дело. К тому же им явно не нравилась перспектива эмиграции в Парфию, что в тех политических условиях автоматически делало невозможным их возвращение в Рим. Среди покинувших Секста был даже его тесть Либон. В это время в регион прибыл и Тиций с кораблями и значительной сухопутной армией. Оказавшись в таких условиях, Секст решил через Малую Азию пробиваться к парфянам. Фурний, Тиций и галатский царь Аминта, выполнявший приказ Антония, стали его преследовать. Секст попытался было выиграть время, заявляя о посылке специального посольства к Антонию, но антониевские полководцы терять времени не захотели и потребовали безоговорочной капитуляции. Тогда Помпей решился на хитрость. Он сделал вид, что остается в лагере, а сам ночью покинул его и направился к морю, чтобы сжечь корабли Тиция. Но перебежчик сообщил об этом антонианцам. Конница Аминты настигла Помпея, и тот предпочел без всяких условий сдаться Тицию. Но Тиций уже имел к этому времени приказ Антония расправиться с Помпеем. Выполняя этот приказ, Тиций отвез пленника в Милет и там приказал убить его. Произошло это уже в 35 г. до н. э., когда Сексту было, вероятно, немногим более 30 лет.

Если шансы на победу в гражданской войне у Гненя Помпея Великого были приблизительно равны с Цезарем и его поражение было в значительной степени обусловлено его собственным характером, то у его сына таких шансов было очень мало. Ресурсы Сицилии, даже вместе с Сардинией, не шли ни в какое сравнение с теми, какими обладали триумвиры. Положение можно было изменить только каким-либо решительным действием, на которое его время от времени толкал Менодор, но Секст на такие действия решался крайне редко. У него практически не было долговременной стратегии, он ограничивался временными успехами, и это сыграло в его судьбе роковую роль. В дипломатии же он не сумел переиграть не только хитроумного Октавиана, которого вообще переиграть в этом деле было чрезвычайно трудно, если не невозможно, но и гораздо более простодушного Антония. В принципе разгром Секста был предрешен.