Recognized melioidosis-endemic areas are widening. In the South Pacific, melioidosis is endemic in New Caledonia, northern Australia, and Papua New Guinea. We report the first 4 documented cases of human melioidosis from New Caledonia. Molecular typing of 2 Burkholderia pseudomallei isolates suggests a link to Australian strains.