Squat lobsters from Madagascar, Vanuatu, Papua New Guinea, Fiji, eastern Australia and French Polynesia belonging to the Agononida incerta (Henderson, 1888) species complex are described as four new species: A. madagascerta, A. polycerta, A. tasmancerta and A. vanuacerta. This brings to ten the number of species in this complex. All species are morphologically distinguishable only on the basis of the shape of the anterolateral margin of the telson and setation of the dactyli of pereopods 2-4. The morphological delineation of nine of the species and their taxonomic status are robustly supported by phylogenetic analysis of the partial 16S rDNA gene and the partial mitochondrial cytochrome oxidase subunit 1 genes, and in some cases by colour. A phylogenetic analysis of the nine species for which molecular data are available grouped the species in two clades, one of four species with facial spines on the upper surface of pereopod 4 and the other of five species lacking facial spines.