По вечерам он читал свои сочинения пиратам, чтобы проверить на них силу своего красноречия. По словам историка, морские разбойники не были покорены поэтическим творчеством пленника. Они просто смеялись над ним и называли римским дураком.
Цезарь в свою очередь платил им откровенностью. Он заявил, что после своего освобождения вернется и казнит всех пиратов до единого. Через 38 дней после пленения римлянина пираты получили известие, что выкуп за Цезаря, равный 50 талантам, оставлен у легата Валерия Торквата. Уже на следующий день Цезарь и его спутники были отправлены на корабле в Милет, где разбойникам и были выплачены деньги. Вновь обретя свободу, Цезарь с энергией, совершенно неожиданной для пиратов, и для его политического соперника Суллы, принялся за осуществление своего плана наказания морских разбойников. Уже на следующий день после вступления на свободный берег Цезарь на четырех галерах, имевших на борту 500 воинов, внезапно напал на пиратов на острове Фармакусса и застиг их врасплох. Он не только не думали столь быстро вновь встретиться своим бывшим пленником, но и были еще пьяны после оргии по случаю дележа добычи. Цезарь пленил около 350 пиратов и получил обратно свои деньги. Он потопил пиратские корабли и доставил пленников в Пергам, резиденцию римского претора Юния. Претора тогда не было в городе, и Цезарь не мог получить у него разрешения на казнь пиратов. Тогда он стал действовать самостоятельно: приказал отобрать 30 вожаков, заковать их в цепи и привести к нему. Он напомнил им о своем обещании распять их на кресте. Однако, сказал он, в благодарность за хорошее отношение к нему во время плена он будет снисходителен: главарям, перед тем как их распять, перережут горло, а простые пираты будут задушены. Так и было сделано.
О том, с какой ненавистью относились после этого к римлянам киликийские пираты, сообщает Плутарх:
"Когда какой-нибудь пленник кричал, что он римлянин, и называл свое имя, они, притворяясь испуганными и смущенными, хлопали себя по бедрам и, становясь на колени, умоляли о прощении. Несчастный пленник верил им, видя их униженные просьбы. Затем одни надевали ему башмаки, другие облачали в тогу, для того-де, чтобы опять не ошибиться. Вдоволь поиздевавшись над ним таким образом и насладившись его муками, они наконец спускали среди моря сходни и приказывали высаживаться, желая счастливого пути, если же несчастный отказывался, то его сталкивали за борт и топили".
Попытка Рима уничтожить морской разбой с помощью военного флота под командованием Публия Сервилия окончилась неудачей. Пиратские либурны были маневреннее, чем тяжелые корабли римлян. Но как только военные корабли скрывались, сыны Киликии вновь выходили, захватывали их суда и брали пленных. Это сказывалось на жизни города. В 67 году до н. э. положение с хлебом в Риме столь ухудшилось, что сенат вынужден был поручить Гнею Помпею возглавить борьбу с пиратами и предоставил ему особые полномочия. Операция считалась настолько сложной, что для ее осуществления Помпей попросил дать ему три года. Он показал себя умелым флотоводцем. По его приказу было построено 500 либурнов, то есть кораблей такого же типа, как и те, на которых плавали пираты. Первоначально Помпей избрал местом своих действий западную часть Средиземного моря. Он разбил этот район на 13 округов и для каждого выделил командира, предоставив в его распоряжение соответствующее количество Кораблей. Сам полководец принял командование над Центральным флотом, который занял выжидательную позицию между Африкой и Сицилией.
Кроме флота, Помпей собрал армию из 12 тыс. пеших легионеров и 5 тыс. всадников. Армия должна была бороться с пиратскими поселениями на побережье. Вся операция была им так хорошо продумана и организована, что уже через 40 дней он смог доложить сенату, что в западной части Средиземного моря с пиратством покончено.
Одержав эту победу, Помпей отправился на восток Средиземноморья, в район, где действовали киликийские пираты. Очевидно предупрежденные об успехах римского полководца, но уверенные в своем превосходстве, они вступили в открытый бой с римским флотом у Коракесия и были разбиты. По дошедшим до нас сведениям, морские разбойники потеряли в этом бою 1300 кораблей, 400 — достались победителям; 20 тыс. пиратов были взяты в плен, 10 тыс.— погибли.