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