Резкое обострение отношений между Октавианом и Антонием, дошедшее до настоящей войны между ними, вызвало недовольство солдат обеих армий и вообще всех цезарианцев, включая, что было особенно важно, ветеранов. Под их давлением оба триумвира пошли на соглашение, которое и было заключено осенью 40 г. до н. э. в Брундизии. Помпей, таким образом, лишился важного союзника по борьбе с Октавианом. В этих условиях Секст был вынужден очистить те пункты Италии, которые он успел захватить, и отойти на Сицилию, но с тем большим упорством он продолжал разорять берега Апеннинского полуострова, не давая никакой возможности поставить туда продовольствие. Это вызвало возмущение в Риме. Все требовали примирения с Помпеем. Когда во время игр процессия внесла статуи богов, римляне особенно горячо стали приветствовать Нептуна, явно намекая на Секста Помпея. Дело дошло до нападения на Октавиана, которого толпа считала главным виновником сложившегося положения. Под угрозой сожжения дома римляне потребовали от Муции, вернувшейся к тому времени в Рим, чтобы она склонила своего сына к миру. Антоний предложил Сексту послать в Рим его тестя Либона, гарантируя ему безопасность. Секст согласился, и Либон отправился в Рим, но, не получив таких же гарантий от Октавиана, хотя тот и был его родственником, остановился на небольшом острове у побережья Кампании. Под давлением общественного мнения Октавиан тоже был вынужден согласиться на переговоры как через посредничество Либона, так и непосредственно с Помпеем. Оба триумвира (о Лепиде уже не было и речи) отправились в Кампанию. Одновременно и ряд советников Помпея настаивали на таких переговорах. Менодор, управлявший Сардинией, призывал Секста или еще энергичнее вести военные действия, чтобы покончить с врагами одним ударом, или заключить мир. И Помпей согласился. Он тоже на своем корабле отправился к берегам Кампании.
Шел уже 39 г. до н. э. Поскольку Помпей не доверял триумвирам и не хотел сойти на берег, а триумвиры, со своей стороны, также не доверяли Сексту и не желали взойти на его корабль, то в море около портового города Путеолы были построены две платформы, разделенные небольшим водным пространством, и на ту, что находилась ближе к берегу, взошли Октавиан и Антоний, а на обращенную в море — Помпей и Либон. Переговоры шли трудно. Помпей выдвинул условия, которые триумвиры принять никак не хотели. В частности, видя, что Лепид фактически отстранен от власти, он настаивал, чтобы его, Помпея, включили в триумвират вместо Лепида. На какое-то время переговоры были прерваны, и обе стороны вернулись ни с чем. Но положение было трудным в обоих лагерях. Угроза все явственнее надвигающегося голода и связанный с этим рост агрессивности римской толпы толкали триумвиров, особенно Октавиана, который по договору в Брундизии управлял всей западной частью республики, включая Италию, на поиски соглашения. А среди сторонников Помпея явно намечался раскол. Опора Помпея была очень разнородной, и между теми остатками римской знати, которые собрались на Сицилии, и основной массой его сторонников, значительная часть которой состояла из бежавших к нему рабов и вольноотпущенников, обострились противоречия. Сам Секст стал очень подозрительно относиться к Мурку, который среди проскрибированных сохранял высокий авторитет. Дело кончилось убийством Мурка, что еще более накалило атмосферу. Для тех членов римского нобилитета, которые бежали к Помпею, самым важным было безопасное возвращение в Рим и восстановление имущества. Они и стали особенно настаивать на возобновлении переговоров. И обе стороны были вынуждены согласиться.