Dès 1855 l'administration coloniale encourage la venue de colons en cédant des terres en concessions agricoles (au détriment des populations locales) mais cela ne paraît pas suffisant. Dans le même temps en Guyane, la situation sanitaire est effroyable. La toute jeune colonie pénitentiaire subit des épidémies de fièvre jaune et de paludisme à répétition, décimant sa population pénale, mais aussi le personnel administratif et de surveillance. Aussi, des études sont entreprises pour évaluer la possibilité de créer un bagne en Nouvelle-Calédonie. Elles mettent en parallèle la salubrité du climat et la fertilité d'un sol propre à recevoir des cultures européennes. D'autre part, la proximité de l'Australie (bel exemple de réussite grâce à l'apport de main d’œuvre pénale) permet de croire que le même succès est possible.

Le 2 septembre 1863, l'Empereur signe au palais de Saint-Cloud le décret ouvrant le territoire de la Nouvelle-Calédonie à l'exécution de la peine des travaux forcés. Le premier convoi, composé de 250 condamnés, part de Toulon le 2 janvier 1864 sur l'Iphégénie, pour arriver en rade de Port-de-France le 9 mai. Quatre mois sont nécessaires pour effectuer le voyage ! Les premiers arrivants sont reçus par le Gouverneur Guillain : « Ouvriers de la Transportation, vous êtes envoyés en Nouvelle-Calédonie pour participer aux travaux importants à exécuter dans la colonie, je vous attendais impatiemment. Votre conduite ici peut faire oublier les funestes égarements ... ». Devant ce bel enthousiasme, accueillis quasiment comme des colons libres, les forçats croient eux aussi au miracle. Dirigés vers l'île Nou, ils sont immédiatement mis au travail pour construire les infrastructures du bagne en devenir. Le deuxième convoi aussitôt décidé part de France le 6 janvier 1866 avec 200 nouveaux condamnés.

D'abord effectué sur des grands voiliers de commerce, le voyage s'effectue ensuite sur des navires mixtes, à vapeur. Les quelques 12 000 milles marins nécessitent entre 4 et 5 mois de navigation sur la moitié des mers du globe. Partis d'un port français (Toulon, mais aussi Brest, Rochefort ou l'île d'Aix), les navires descendent l'Atlantique Sud, avec une première escale à Dakar ou Gorée. Ensuite deux possibilités : la traversée vers Santa-Catarina pour y faire des provisions de vivres et trouver des vents favorables jusqu'au cap de Bonne-Espérance, ou la route directe vers le Cap et l'océan Indien, qui sera utilisée lorsque des épidémies de fièvre jaune séviront au Brésil. A une vitesse moyenne de 6 nœuds (10km/h), il faut compter entre 105 et 147 jours de mer pour couvrir la distance. Les conditions de vie à bord sont dures, sans être inhumaines : sous les ordres du commandant, les condamnés sont soumis au régime disciplinaire de la marine. Leur nourriture est la même que celle des matelots, mais ils sont enfermés dans de grandes cages à l'entrepont, ne bénéficiant que d'une promenade par jour. Invariablement, la partie la plus dure du voyage est la navigation dans les mers australes où les condamnés, mal équipés, souffrent généralement du froid. Le premier convoi met 123 jours pour relier Toulon à Nouméa. Avec les navires à vapeur et le passage par le canal de Suez, les derniers voyages sont beaucoup plus courts : 58 jours pour le 75e et ultime convoi, parti de Saint-Martin-de-Ré en décembre 1897.

En 1867, la situation sanitaire en Guyane est toujours aussi catastrophique. Il est donc décidé que seuls les condamnés coloniaux continueront à être envoyés vers le Maroni. Conséquence de cette restriction pour la Nouvelle-Calédonie : les effectifs explosent. Dans le même temps, il faut trouver du personnel pour surveiller ces forçats du bout du monde. Désormais, plus besoin d'être ancien sous-officier de la coloniale ou de la marine, il suffit seulement d'être âgé de 25 à 40 ans, de savoir lire et écrire et de justifier d'une bonne conduite. De nouveaux lieux sont affectés à l'accueil des condamnés : l’îlot Brun, Ducos, Bourail, où un « couvent » (en fait un pénitencier tenu par les sœurs de Saint-Joseph-de-Cluny) est installé pour recevoir les femmes destinées à devenir les épouses des futurs colons. Les concessions rurales (agricoles) et urbaines (artisans) se multiplient. Le travail forcé se retrouve sur tous les centres mais également sur les mines, au camp forestier de Prony, à la conserverie de Ouaco ou à la ferme de Koé.

Entre 1864 et 1872, ce sont environ 4 000 condamnés aux travaux forcés qui sont acheminés. Ces derniers sont divisés en 4 classes : La 4^e est la plus dure, elle est dite « de correction ». Y sont incorporés les nouveaux arrivants aux dossiers impressionnants, les punis, les évadés, qui peuvent même être enchaînés. La 3^e classe sert de transition pour les fortes têtes en cours d'amendement. A eux aussi les travaux les plus durs. La 2^d comprend les transportés qui n'ont pas fait l'objet de punitions depuis plus d'un an. Ils reçoivent un pécule pour leur salaire et travaillent le plus souvent dans les champs ou aux constructions légères. La 1^re classe enfin reçoit les condamnés les plus « méritants », en qui l'administration a toute confiance et qui travaillent dans des familles ou comme ouvrier d'art. De 1866 à 1877, les « chapeaux de paille » (surnom des forçats) participent largement à l'urbanisation de la ville de Nouméa (construction de quais, arasement de la butte Conneau en 1876, percement de voies...). Un certain nombre d'édifices, encore visibles aujourd’hui, sont l’œuvre des bagnards : le kiosque à musique, la cathédrale Saint-Joseph et le temple protestant. Dans les années 1880, ils sont utilisés au développement du réseau routier et ferroviaire de l’île. L'administration pénitentiaire, la Tentiaire, représente à son apogée 700 agents encadrant 10 500 condamnés et 4 600 libérés dépendant de l'administration.

On doit à Allan Hugues, capitaine au long cours et photographe, les plus beaux clichés sur le bagne de Nouvelle-Calédonie. On voit ici le camp de l'île Nou, constitué de grandes cases bien alignées de part et d'autre d'une grande allée centrale baptisée ironiquement le Boulevard du crime. Il s'agit de dortoirs d'environ 20 mètres de longs dans lesquels sont entassés 80 forçats.

Lorsque la France annexe l'archipel en 1853, elle n'est peuplée que d'environ 40 000 Kanaks. Il faut donc trouver des colons pour la mettre en valeur. Ainsi, le gouverneur Guillain accorde 300 hectares de terre à titre gratuit à tout nouvel arrivant. Une vingtaine de paysans bretons constitueront ce que l'on appellera « la phalange océanienne ». Mais le plus gros de l'effort de colonisation est mené pour et par l'administration pénitentiaire avec un tri des condamnés les plus aptes à travailler dans l'objectif clairement avoué d'obtenir le même succès que les Anglais en Australie. Les condamnés de 1^re classe peuvent, avant même d'être libérés, obtenir des concessions de terrains agricoles (ou des concessions urbaines). Toutefois les bagnards ne sont pas forcément des paysans. C'est pourquoi, dans l'optique d'une réhabilitation, l'administration pénitentiaire crée des centres agricoles de formation. Mais la première erreur va être de les garder dépendant de l'administration, tant pour leur approvisionnement que pour la vente de leurs produits, limitant ainsi tout esprit d'initiative. D'abord cantonnés à l'île Nou, les concessions agricoles se multiplient et s'agrandissent : Bourail, Ducos, Téremba (près de la rivière La Foa), Canala…