The genus Khaya includes some of the highest-value timber species in natural forests in Africa, which are under heavy exploitation pressure. Genetic identification of Khaya species is important to confirm the taxonomic classification for biodiversity conservation purposes and as a forensic tool aiding law enforcement in the fight against illegal logging. We collected samples from a total of 2222 trees belonging to five or six (depending on classification) different Khaya species (K. ivorensis, K. anthotheca/K. nyasica, K. grandifoliola, K. senegalensis, K. madagascariensis). Representative sampling was conducted over the natural ranges of all sampled Khaya species, in humid tropical forest and savanna zones. We genotyped individuals based on 101 molecular markers (67 nuclear, 11 chloroplast and 22 mitochondrial SNPs, 1 chloroplast indel). Bayesian clustering produced three main genetic groups assigning all K. ivorensis and all K. senegalensis trees, respectively, in two different clusters and all remaining individuals in a third cluster. Genetic self-assignment tests with all 101 SNPs had success rates of 97–100% for all species except for K. nyasica and K. madagascariensis, which could not be clearly distinguished from each other. A success rate for species identification nearly as high was observed using a subset of 15 highly differentiated SNPs. There was only very little evidence for hybridization among species and the vast majority (> 97%) of individuals were assigned to the same species group as identified based on morphological characters.