Поскольку Помпея нельзя было победить иначе как на море, Цезарь приказал строить корабли в Риме и в Равенне. В 38 г. до Р.Х., когда все было готово, он переправился из Тарента в Регий. Помпей ждал его у Мессены всего с 40 кораблями (нападение произошло неожиданно, и главные силы еще не успели к нему подойти). Цезарь, однако, не решился завязывать сражение в узком проливе. К тому же он поджидал флот Менодора. От Регия он поплыл на север вдоль берегов пролива. Между тем Помпей, успевший собрать большую часть своих кораблей, настиг флот Цезаря у Схиллея и прижал его к скалистому неприступному берегу. Корабли стали наталкиваться друг на друга, налетать на скалы и наполняться водой. Ночь и подход кораблей Менодора не позволили Помпею довершить разгром, но и без того положение флота Цезаря было отчаянное.
Сам он соскочил с корабля на прибрежные скалы, принимал выплывавших из моря и провожал их на ближайшую гору. Спасшиеся провели ночь на голом скалистом берегу, без пищи и слуг, испытав все лишения. Цезарь, находившийся в таком же положении, обходил их, убеждая потерпеть до зари. Все его рабы разбежались, и у него поначалу даже не было палатки, где бы он мог отдохнуть. На другой день разразилась сильнейшая буря. Помпей успел укрыться со своими кораблями в Мессене, а флот Цезаря был почти полностью уничтожен непогодой (Аппиан: 17; 3, 12, 19, 22, 24, 30-34, 47-52, 56, 65-69, 71-72, 77, 80, 84-90).
Среди этих несчастий произошло радостное для Цезаря событие — после многих неудач, он наконец нашел себе спутницу жизни. В юности он был помолвлен с дочерью Публия Сервилия Исаврика. Однако после первого примирения с Антонием, когда их воины потребовали, чтобы оба полководца вступили в родственную связь, Цезарь взял в жены Клавдию, падчерицу Антония, дочь Фульвии от Публия Клодия, хотя она едва достигла брачного возраста. Поссорившись со своей тещей Фульвией, Цезарь, не тронув жены, отпустил ее девственницей. Вскоре он женился на Скрибонии, которая уже была замужем за двумя консулами и от одного имела детей; но и с нею он развелся в самый день рождения дочери Юлии, как он сам писал, «устав от ее дурного нрава». Теперь же Цезарь увлекся Ливией Друзиллой, женой Тиберия Нерона. Он отнял ее беременной у мужа, женился на ней, и любил ее, как никого, почитая до самой смерти (Светоний: «Август»; 62).
В следующем году война с Помпеем продолжалась. В крайности Цезарь вынужден был обратиться за помощью к Антонию. В начале весны 37 г. до Р.Х. Антоний приплыл для переговоров в Тарент. Поначалу отношения между соправителями были натянутые: Цезарь жаловался, что Антоний задержал свою помощь на такой долгий срок. Антоний послал вперед себя жену, и Октавия сумела смягчить брата. Триумвиры встретились вполне дружелюбно. Цезарь один без телохранителей переплыл в лодке реку Тарент и провел в доме Антония ночь. На следующий день такое же доверие выказал со своей стороны Антоний. Договорились, что Антоний даст Цезарю 120 боевых кораблей для войны с Помпеем, а Цезарь уступит ему 20 000 легионеров для похода против парфян. Свою чрезвычайную власть они продлили еще на пять лет и не старались придать этому решению даже той видимости законности, о которой заботились в первый раз (Аппиан: 17; 93-95).
Отложив начало войны еще на год, Цезарь занялся подготовкой своего флота. Взамен погибших кораблей были отстроены новые. Убыль в экипажах была восполнена за счет 20 000 отпущенных на волю рабов. При Байях Цезарь велел устроить гавань, соединив с морем Лукринское и Авернское озера, и здесь в течение всей зимы тренировал свои войска (Светоний: «Август»; 16).
Наконец, летом 36 г. до Р.Х. Цезарь во второй раз выступил против Помпея. Сам он вел флот из Дикеархии, Лепид с 170 кораблями и 12 легионами направился из Африки к Лилибею, а Тавр с флотом Антония шел из Тарента. По всеобщему мнению, отразить этот тройной удар Помпею было не под силу. Однако вновь, как и два года назад, сильная буря смешала все планы Цезаря. Тавр, правда, успел вернуться в Тарент при первых ее признаках, а Лепид, потеряв много кораблей, все же добрался до Сицилии, но флот самого Цезаря понес такие потери и повреждения, что ему пришлось потратить целый месяц на ремонт кораблей. Цезарь с твердостью воспринял эту новую неудачу. Хотя приближались осень и конец навигации, он решил завершить войну с Помпеем в этом году. Свой флот под командованием Агриппы он отправил к Милам, а сам с кораблями Тавра поплыл к Тавромению.
Агриппа в Милах встретил флот Помпея и атаковал его. После Упорного боя помпеянцы, потеряв 30 своих кораблей и потопив 5 неприятельских, отступили на более мелкое место, куда корабли Агриппы не могли за ними следовать. Цезарь тем временем высадил три легиона под Тавромением. Он был уверен, что Помпей все еще находится под Милами, но тот, оставив там часть кораблей, чтобы вводить в заблуждение Агриппу, внезапно явился под Тавромением и стал теснить врага. Цезарь велел войску ожидать его в укрепленном лагере, а сам с флотом вышел против Помпея. Битва продолжалась целый день и закончилась полным разгромом Цезаря. Большая часть его кораблей была потоплена или сожжена. Другие бежали к берегам Италии.
Сам Цезарь добрался до Абальского залива (Аппиан: 17; 98-99, 105, 107, 109-112). Военачальники Помпея, Демохар и Аполлофан, преследовали его, и он с трудом ускользнул от них на единственном корабле (Светоний: «Август»; 16). Цезарь сошел на берег с одним только оруженосцем — без друзей, телохранителей и рабов. Здесь его, ослабевшего телом и духом, нашли разведчики Мессалы (ему поручил Цезарь в свое отсутствие италийские легионы). Ободрившись, Цезарь стал деятельно собирать корабли и готовить к переправе новые легионы (Аппиан: 17; 112). В эти дни его жизнь не раз подвергалась опасности. Рассказывают, что один раз он шел пешком мимо Локров в Регий и увидел биремы Помпея, двигавшиеся вдоль берега; приняв их за свои, он спустился к морю и едва не попал в плен. А когда после этого он спасался бегством по узким тропинкам, то раб его спутника Эмилия Павла попытался его убить, воспользовавшись удобным случаем, чтобы отомстить за Павла-отца, казненного во время проскрипций (Светоний: «Август»; 16).
Те войска, которые он оставил под Тавромением, вынуждены были выйти из лагеря из-за недостатка продовольствия. С тяжелыми боями, постоянно теснимые помпеянцами, они через безводную местность добрались до Мил и соединились с Агриппой. К этому времени Агриппа овладел Тиндаридой, местечком, изобиловавшим съестными припасами и удобно расположенном для ведения войны на море.
Цезарь переправил в Тиндариду свои войска. Всех сил в Сицилии у него было 21 легион тяжеловооруженных, 20 000 всадников и 5000 легковооруженных. Уже глубокой осенью во время сильных дождей он соединился с войском Лепида, и они оба расположились лагерем близ Мессены. Их отряды рассыпались по всей Сицилии, подвергая ее грабежам и опустошению.
