La pêche du corail était de tradition séculaire chez les Corses; ils étaient au courant de l'organisation que lui avaient donnée les Génois; désireux de s'affranchir du joug de Gênes, un certain nombre d'entre eux émigrèrent à Marseille, où Lenche, dont le vrai nom est probablement Lencio, fonda la première Compagnie du corail, dans laquelle entrèrent beaucoup de nobles marseillais, en particulier Jean Riquetti, ancêtre des Mirabeau. La Compagnie marseillaise obtint le privilège de la pêche du corail sur toutes les côtes de Barbarie, depuis Montefousque (le cap Mafetouche près du cap de Fer) jusqu'au cap Nègre en face de Tabarka, en vertu de lettres royales de 1553 et d'un commandement du Grand Seigneur de 1582. Dès 1564, la Compagnie apparaît fortement constituée et recrutée dans l'élite du commerce marseillais.

Les établissements appelés " les Concessions d'Afrique " sont-ils aussi anciens que la Compagnie elle-même ? Nous l'ignorons. Par la suite, elle eut quatre établissements fixes : Bône, la Calle (Mersa-el-Kharez, le port aux breloques), le Bastion-de-France et le cap Rose. Le Bastion-de-France, centre des opérations de la Compagnie, s'élevait à dix kilomètres à l'Ouest de la Calle, à égale distance entre ce port et celui de Bône ; on y voit encore les restes d'une tour qui s'élevait sur un escarpement rougeâtre, au-dessus d'une petite anse bordée de sable blanc; tout près de là se trouve le lac Melah, appelé autrefois l'étang du Bastion, qui communiquait avec la mer par un chenal. Il y avait au Bastion une petite garnison, un approvisionnement de poudre, des arquebuses et même de l'artillerie. Le chef des établissements marseillais, directeur général de toutes les opérations en Algérie, y résidait, ainsi que l'écrivain son lieutenant; des gens de métier, des soldats commandés par un chef appelé caporal, au total une centaine d'hommes, sans compter les corailleurs, formaient la population du Bastion.

La localité était des plus insalubres et la mortalité très grande. On s'efforçait pourtant de bien traiter les employés et la garnison. Tout venait de France, sauf la viande, le pain et les fèves; on leur apportait du poisson salé, du vin et l'huile d'olive nécessaire à toute cuisine provençale. La Compagnie payait aux Turcs un tribut de 1 500 écus d'or et faisait de nombreux cadeaux aux caïds et aux chefs de la région, qui eux-mêmes étaient souvent des renégats corses ou provençaux comme Ramdan, originaire de Nice, qui fut longtemps caïd de Bône.