The Cotesia flavipes complex of parasitoid wasps (Hymenoptera: Braconidae) are economically important for the biological control of lepidopteran stemboring pests associated with gramineous crops. Some members of the complex successfully parasitize numerous stemborer pest species, however certain geographic populations have demonstrated variation in the range of hosts that they parasitize. In addition, the morphology of the complex is highly conserved and considerable confusion surrounds the identity of species and host-associated biotypes. We generated nucleotide sequence data for two mtDNA genes (COI, 16S) and three anonymous nuclear loci (CfBN, CfCN, CfEN) for the C. flavipes complex. To analyze genetic variation and relationships among populations we used (1) concatenated mtDNA and nDNA data, (2) a nDNA multilocus network approach, and (3) two species tree inference methods, i.e. Bayesian estimation of species trees (BEST) and Bayesian inference of species trees from multilocus data with (*)BEAST. All phylogenetic analyses provide strong support for monophyly of the complex and the presence of at least four species, C. chilonis (from China and Japan), C. sesamiae (from Africa), C. flavipes (originating from the Indo-Asia region but introduced into Africa and the New World), and C. nonagriae (from Australia and Papua New Guinea). Haplotype diversity of geographic populations relates to historical biogeographic barriers and biological control introductions, and reflects previous reports of ecological variation in these species. Strong discordance was found between the mitochondrial and nuclear markers in the Papua New Guinea haplotypes, which may be an outcome of hybridization and introgression of C. flavipes and C. nonagriae. The position of Cotesia flavipes from Japan was not well supported in any analysis and was the sister taxon to C. nonagriae (mtDNA, (*)BEAST), C. flavipes (nDNA) or C. flavipes+C. nonagriae (BEST) and, may represent a cryptic species. The concatenated five gene phylogenetic analyses did not support the overall separation and monophyly of clades associated with different host species, although some clades did show specific host associations, possibly due to localized host availability, rather than host specificity. Our results provide a framework for assessing whether distinct lineages represent cryptic species, and for examining parasitoid-host evolution and compatibility more generally. Given the limitations of morphological based identification for members of this complex, molecular identification is recommended prior to any biological control introductions.