The following acanthocolpid species are reported from New Caledonia. Acaenodera nautili sp. n. from Conger cinereus Rüppel differs from other Acaenodera species in details of the body-spination, the sucker-ratio and the bipartite seminal vesicle; Stephanostomum murielae sp. n. from Carangoides hedlandensis (Whitley) differs from most species of Stephanostomum in the average of 36 circum-oral spines, the circum-oral spine rows with a ventral hiatus and the anterior extent of the vitellarium being >10% of the hindbody length from ventral sucker. The species is distinguished from the three other species with these characters in a detailed review. The other species reported are: Stephanostomum aaravi Bray et Cribb, 2003 from Lethrinus miniatus and L. rubrioperculatus; Stephanostomum ditrematis (Yamaguti, 1939) from Gnathanodon speciosus; Stephanostomum japonocasum Durio et Manter, 1969 from Cephalopholis urodeta, Epinephelus areolatus, E. chlorostigma, E. maculatus, E. retouti, Lethrinus miniatus and Variola louti; Stephanostomum uku Yamaguti, 1970 and Pleorchis uku Yamaguti, 1970 from Aprion virescens.