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