Философа Гая Блоссия из Кум, наиболее стойкого приверженца Тиберия, оптиматы хотели предать особому суду, превратив его в политический процесс над всеми гракхианцами, но тому удалось бежать из-под стражи. Требаций встретился с ним уже в Пергаме, захваченном гелиополитами Аристоника.
В то время многие римские изгнанники искали спасения в охваченном восстаниями Пергамском царстве. Гай Блоссий стал советником Аристоника и проповедником коммунистических идей Ямбула и Эвгемера среди восставших, которые стали называть себя гелиополитами. Требаций и его друзья, имевшие большой опыт в морском деле, помогали восставшим собирать флот и обучать матросов. Они приняли участие в ожесточенном морском бою против каппадокийского флота, который был уничтожен восставшими, причем убит был и царь Каппадокии Ариарат.
Однако вскоре у берегов Пергама появился большой флот понтийского царя Митридата. Гелиополиты, потерявшие много кораблей в сражении с каппадокийцами, не смогли воспрепятствовать Митридату высадить войско близ восставшей столицы. Понтийцы взяли город приступом, устроив в нем ужасающую резню.
Когда пала Стратоникея – столица восставших – и Аристоник был захвачен в плен римлянами, Гай Блоссий не стал больше испытывать судьбу и покончил с собой, бросившись на меч. Требаций же уговорил своих товарищей идти к Балеарским островам, где он надеялся найти приют у гнездившихся там пиратов.
Изгнанники располагали одиннадцатью легкими кораблями, на которых они и совершили плавание к Балеарам. Обосновавшись там, они в течение восьми лет избороздили все Внутреннее море, грабили торговые суда и охотились за римскими сенаторами. Немало оптиматов попало тогда в плен к Требацию, но только немногих из них он отпустил за большой выкуп. Остальные, запятнавшие себя кровью Тиберия Гракха и его сподвижников, были по его приказу утоплены в море. Двух пленников, участвовавших в расправе над его другом Гаем Биллием, Требаций убил собственноручно.
Сципиона Назику он готов был преследовать не только на море, но и на суше. Ненавидимый и презираемый своими же гражданами в Риме за организованное им убийство народного трибуна, Назика ушел в добровольное изгнание. Он хотел найти успокоение там, где еще недавно искали убежище Гай Блоссий и прочие гракхианцы. Но смерть настигла его раньше, чем он добрался до Пергама. Обстоятельства его кончины остались неизвестными. Ходили слухи, что он умер насильственной смертью. Потом в Риме узнали о гибели бывшего народного трибуна Публилия Руфа, одного из противников и убийц Тиберия Гракха. Во время морского путешествия он попал в руки Требация, который приказал казнить его особо изощренным способом: убийцу народного трибуна утопили в море, зашив его в мешке вместе с петухом, собакой, змеей и обезьяной. По римскому обычаю, так казнили отцеубийц. Таким же способом пираты расправлялись и с предателями из своей среды.
Действия балеарских пиратов становились все более опасными для Рима. Всадническое сословие, благосостояние которого во многом зависело от морской торговли, требовало положить конец пиратству.
Наконец консул Квинт Цецилий Метелл, отец будущего Метелла Нумидийского, по приказу сената собрал большой флот и двинулся к Балеарским островам. Пиратские стоянки Метелл уничтожил, после чего приступил к завоеванию самих островов. В Рим он вернулся победителем и, справив морской триумф, получил почетное прозвище «Балеарский».
Требацию удалось вывести свои корабли из-под удара римлян, и вскоре они пристали к южному берегу Крита, недалеко от устья реки Электры. Это было не совсем удобное место для стоянки больших судов, но опытный глаз Требация разглядел у громоздившихся высоких известняковых скал несколько песчаных отмелей, на которые во время бури можно было вытаскивать легкие пиратские корабли.
С коренными жителями Крита пришельцы быстро поладили. Критские города сами занимались морским разбоем, охотно принимая у себя наемников из чужеземных храбрецов, не боявшихся моря и умевших владеть оружием.
Поначалу Требаций и все прибывшие с ним римские изгнанники поступили на службу городу Гортине, который тогда нуждался в боевых кораблях для охраны своих торговых судов. Это избавило их от рискованной конфронтации с критскими аборигенами.
Договор, заключенный с гортинцами, обязывал бывших балеарских пиратов делиться с ними захваченной добычей. Однако беглецы из Рима продолжали считать себя частью того гордого народа, который привык повелевать другими и никому не подчиняться. Казна их быстро пополнилась за счет добычи от удачных походов к берегам Греции и Италии. Через год она уже насчитывала около ста двадцати талантов. Эти деньги Требаций и его сподвижники решили использовать для основания своей собственной колонии.