Отложив начало войны еще на год, Цезарь занялся подготовкой своего флота. Взамен погибших кораблей были отстроены новые. Убыль в экипажах была восполнена за счет 20 000 отпущенных на волю рабов. При Байях Цезарь велел устроить гавань, соединив с морем Лукринское и Авернское озера, и здесь в течение всей зимы тренировал свои войска (Светоний: «Август»; 16).
Наконец, летом 36 г. до Р.Х. Цезарь во второй раз выступил против Помпея. Сам он вел флот из Дикеархии, Лепид с 170 кораблями и 12 легионами направился из Африки к Лилибею, а Тавр с флотом Антония шел из Тарента. По всеобщему мнению, отразить этот тройной удар Помпею было не под силу. Однако вновь, как и два года назад, сильная буря смешала все планы Цезаря. Тавр, правда, успел вернуться в Тарент при первых ее признаках, а Лепид, потеряв много кораблей, все же добрался до Сицилии, но флот самого Цезаря понес такие потери и повреждения, что ему пришлось потратить целый месяц на ремонт кораблей. Цезарь с твердостью воспринял эту новую неудачу. Хотя приближались осень и конец навигации, он решил завершить войну с Помпеем в этом году. Свой флот под командованием Агриппы он отправил к Милам, а сам с кораблями Тавра поплыл к Тавромению.
Агриппа в Милах встретил флот Помпея и атаковал его. После Упорного боя помпеянцы, потеряв 30 своих кораблей и потопив 5 неприятельских, отступили на более мелкое место, куда корабли Агриппы не могли за ними следовать. Цезарь тем временем высадил три легиона под Тавромением. Он был уверен, что Помпей все еще находится под Милами, но тот, оставив там часть кораблей, чтобы вводить в заблуждение Агриппу, внезапно явился под Тавромением и стал теснить врага. Цезарь велел войску ожидать его в укрепленном лагере, а сам с флотом вышел против Помпея. Битва продолжалась целый день и закончилась полным разгромом Цезаря. Большая часть его кораблей была потоплена или сожжена. Другие бежали к берегам Италии.
Сам Цезарь добрался до Абальского залива (Аппиан: 17; 98-99, 105, 107, 109-112). Военачальники Помпея, Демохар и Аполлофан, преследовали его, и он с трудом ускользнул от них на единственном корабле (Светоний: «Август»; 16). Цезарь сошел на берег с одним только оруженосцем — без друзей, телохранителей и рабов. Здесь его, ослабевшего телом и духом, нашли разведчики Мессалы (ему поручил Цезарь в свое отсутствие италийские легионы). Ободрившись, Цезарь стал деятельно собирать корабли и готовить к переправе новые легионы (Аппиан: 17; 112). В эти дни его жизнь не раз подвергалась опасности. Рассказывают, что один раз он шел пешком мимо Локров в Регий и увидел биремы Помпея, двигавшиеся вдоль берега; приняв их за свои, он спустился к морю и едва не попал в плен. А когда после этого он спасался бегством по узким тропинкам, то раб его спутника Эмилия Павла попытался его убить, воспользовавшись удобным случаем, чтобы отомстить за Павла-отца, казненного во время проскрипций (Светоний: «Август»; 16).
Те войска, которые он оставил под Тавромением, вынуждены были выйти из лагеря из-за недостатка продовольствия. С тяжелыми боями, постоянно теснимые помпеянцами, они через безводную местность добрались до Мил и соединились с Агриппой. К этому времени Агриппа овладел Тиндаридой, местечком, изобиловавшим съестными припасами и удобно расположенном для ведения войны на море.
Цезарь переправил в Тиндариду свои войска. Всех сил в Сицилии у него было 21 легион тяжеловооруженных, 20 000 всадников и 5000 легковооруженных. Уже глубокой осенью во время сильных дождей он соединился с войском Лепида, и они оба расположились лагерем близ Мессены. Их отряды рассыпались по всей Сицилии, подвергая ее грабежам и опустошению.
Помпей не решался начать сухопутное сражение. Гордясь своим флотом, он послал к Цезарю вызов и предложил решить исход войны морской битвой. Цезарь согласился, хотя прежде ему не везло ни в одном его морском предприятии. Был назначен день, к которому обе стороны снарядили по 300 кораблей. Цезарианским флотом командовал Агриппа, наиболее талантливый из всех полководцев Цезаря. Цезарь поверил в его удачу и не ошибся. На виду у двух сухопутных армий вблизи Навлоха развернулось грандиозное морское сражение, протекавшее с большим ожесточением. Исход его долго казался неясным, но в конце концов Агриппа прижал помпеянский флот к берегу и полностью уничтожил. Успели спастись только 17 кораблей. Помпей укрылся в Мессену, бросив свою сухопутную армию. В тот же день она сдалась Цезарю. Когда весть о поражении достигла Лилибея, его гарнизон также капитулировал. Помпей бежал из Сицилии. Восемь легионов, оставленные им в Мессене, перешли на сторону Лепида.
Располагая теперь 22 легионами, Лепид стал строить планы, каким образом он может сохранить Сицилию для себя, не отдавая ее Цезарю. Он послал приказ во все города, в которых уже стояли его гарнизоны, не впускать к себе ни Цезаря, ни его полководцев. Таким образом, только что закончив одну войну, Цезарь оказался перед угрозой новой.
Впрочем, скоро выяснилось, что Лепид не рассчитал своих сил. Даже его собственные солдаты не одобряли его распри с Цезарем. Что же касается недавних помпеянцев, только что перешедших на его сторону, то их такой оборот дела устраивал еще меньше, ведь в случае поражения Лепида они уже никак не могли рассчитывать на снисхождение со стороны Цезаря. Зная о настроениях солдат, Цезарь с незначительной охраной вдруг явился в лагерь Лепида. Он обратился к солдатам и сказал, что не желает войны. Те приветствовали его как императора, а помпеянцы тотчас перешли на его сторону. Узнав в чем дело, Лепид напал на Цезаря. В завязавшейся схватке некоторые спутники его были убиты, самого Цезаря ударили копьем, но не пробили панциря. Он поспешно отступил за укрепления.
Однако дерзкий его поступок не прошел без последствий. Воины Лепида стали перебегать к Цезарю, сначала по одиночке, потом группами, и наконец целыми легионами. Цезарь принимал всех. Когда его спросили, что делать с Лепидом, он велел сохранить ему жизнь. Он лишил Лепида всех полномочий и отпустил в Рим, где тот жил до смерти как частный человек. Африка и Сицилия были присоединены к владениям Цезаря. Так счастливо закончилась эта война, самая тяжелая из всех, какие пришлось вести Цезарю.
Возвратившись в Рим, Цезарь обратился к делам государства. Он простил все недоимки по налогам и откупам, чем вызвал всеобщую радость и ликование. Но это был только первый шаг. Цезарь понимал, что много надо сделать для того, чтобы вернуть разоренной до последних пределов стране былое процветание. Италия была наводнена шайками беглых рабов, мародеров и отщепенцев всякого рода. Наглость грабителей не знала пределов. Цезарь повел против них настоящую войну и предал всех пойманных массовому истреблению. Не прошло и года, как снова повсюду установились мир и безопасность, и Цезарь заслужил общее изумление столь быстрым и неожиданным восстановлением порядка. Он вернул многие права в государственном управлении ежегодным должностным лицам, согласно отцовским законам, сжег документы, относящиеся ко времени смут, и обещал вполне восстановить государственный строй после возвращения Антония из парфянского похода. Сам Цезарь стал готовиться к походу против иллирийцев, которые своими набегами опустошали берега Италии (Аппиан: 17; 113-126, 129, 132). Он двинулся в Иллирию в 35 г. до Р.Х. Многие племена на побережье подчинились ему без боя. С другими ему пришлось вести упорную борьбу. К 33 г. завоевание Иллирии было завершено (Аппиан: 9; 16-28).
Тем временем постепенно назревала война с Антонием. Тот жил в Александрии и, охваченный любовью к египетской царице Клеопатре, совершенно потерял голову. Мало того, что он наносил оскорбление своей жене и сестре Цезаря, открыто сожительствуя с другой женщиной, он вызвал к себе волну ненависти со стороны римлян еще и тем, что поделил восточные провинции Римской державы между своими детьми от нее. Своего старшего сына Александра он провозгласил царем Армении, Мидии и Парфии, а младшего, Птолемея, — царем Финикии, Сирии и Киликии. Донося об этом сенату и часто выступая перед народом, Цезарь ожесточил римлян против Антония. Не оставаясь в долгу, Антоний посылал своих людей с ответными обвинениями. Важнейшие из них были таковы. Во-первых, отняв у Помпея Сицилию, Цезарь не выделил части острова ему, Антонию. Во-вторых, он не вернул суда, которые занял у Антония для войны с Помпеем. В-третьих, лишил власти Лепида и сам распоряжался его войском, его провинцией и назначенными ему доходами. И, наконец, чуть ли не все земли в Италии он поделил между своими воинами, солдатам же Антония не оставил ничего. Оправдываясь, Цезарь заявлял, что Лепида он отрешил от власти за наглые бесчинства, что военною добычею готов поделиться с Антонием, если и тот поделится с ним своим завоеванием — Арменией, и что на Италию у солдат Антония никаких притязаний быть не может: ведь в их распоряжении Мидия и Парфия, земли, которые они присоединили к Римской державе, отважно сражаясь под начальством своего императора.