L'agent de la République Eglantine a été arrêté et emprisonné à la Conciergerie, à Paris. Gavroche est envoyé dans la capitale pour demander de l'aide au Fantôme, chef des truands de la ville. Mais cedernier n'accepte qu'à une condition, c'est que Gavroche doit aller dans le Pacifique Sud, en Nouvelle Calédonie pour y délivrer un détenu du bagne, Jules Calonec.