Основной базой пиратов считался в то время Мадагаскар. Пиратских поселений там было несколько, и далеко не все их жители разбойничали на морях. Многие занимались торговлей, сельским хозяйством, другие служили у местных вождей, которые часто враждовали между собой. Пришлые же европейцы выступали как военные советники и даже командиры. Во время крейсирования «Приключения» у берегов Мадагаскара несколько матросов Кидда сбежали к пиратам, но бежали они не к очередному Моргану, Дрейку или Флинту, а в существовавшую на севере Мадагаскара республику пиратов Либерталию — первое в мире государство, построенное по принципам раннесоциалистических утопий Томаса Мора и Томмазо Кампанеллы!
Основателями первого в мире социалистического государства были офицер французского флота Миссон и бывший доминиканский монах из Генуи Караччиоли. О них известно очень и очень немного: оба служили на корабле «Победа», который в начале 90-х годов XVII века был направлен в Карибское море с задачей охранять французское торговое судоходство от нападений англичан. В тяжелейшем бою с английским корсаром у острова Мартиники из всех офицеров корабля в живых остался только Миссон, и как только «Победа» взяла верх в сражении, Миссон обратился к оставшимся в живых матросам с предложением бросить военную службу и стать вольными пиратами. Экипаж, уже давно находившийся под влиянием Миссона и служившего здесь же матросом Караччиоли, откликнулся с радостью.
Их пиратство вызывало изумление у всех, кто попадал под их абордаж: никого не убивали, не пытали и старались отбирать только те товары, которые были нужны для дальнейшего плавания. Исключение составляли только работорговые суда — их Миссон грабил без всякой жалости, а рабов освобождал. Вскоре пираты, энтузиазм которых подогревался речами Миссона и Караччиоли, осознали свою исключительность как апостолов новой жизни, и сознание этого настолько поднимало их в собственных глазах, что у Миссона не возникало никаких конфликтов с командой ни по каким причинам. Мало того, к нему начали перебегать моряки с захваченных кораблей разных государств и через некоторое время полностью вливались в его ряды.
Сначала Миссон остановился на Коморских островах, но по неизвестным причинам потом перебрался на Мадагаскар. Либерталия была заложена в бухте Диего-Суарес на северо-восточной оконечности острова, а базы настоящих пиратов находились южнее.
С Мадагаскара Миссон разослал письма пиратам «семи морей» с приглашением присоединиться к нему и строить Свободный город. Надо отметить, что призыв Миссона нашёл отклик среди многих моряков, как пиратов, так и не пиратов, и в короткий срок население Либерталии значительно выросло. О популярности и широкой известности как идей равенства, так и местонахождения Либерталии можно судить по таким документально подтверждённым фактам, как бегство в Либерталию части экипажа «Приключения» вместе с частью добычи, а также приход к Миссону известного карибского пирата Тью, который отдал республике свой корабль и верно служил ей до самого конца.