Members of the tribe Palicoureeae of the coffee family (Rubiaceae) have a complex taxonomic history and have been the focus of few modern systematic studies. The tribe comprises about 1,100 tropical species in ten genera. To investigate phylogeny, we used a target capture approach and the angiosperm-wide Angiosperms353 bait set to produce genomic data for a representative taxon sample of Palicoureeae, with particular focus on the African genus Hymenocoleus. Using coalescent-based inference methods, we find that Puffia gerrardii (recently separated from Geophila) is sister to Hymenocoleus. The deepest split in Hymenocoleus is highly affected by incomplete lineage sorting, possibly as a consequence of rapid speciation during the early evolution of the clade. Remaining interspecific relationships in Hymenocoleus could be confidently resolved and while Robbrecht’s traditional infrageneric classification scheme based on floral features is not supported as reflecting evolution in the group, we find that several other features do, e.g. characters of pyrenes and involucral cups. Although not free of challenges, a strong advantage with our analytical approach is that gene tree heterogeneity can be taken into account. Including flanking regions yielded data sets that had the strongest power to reject polytomies and produced less gene tree error, resulting in species trees with higher normalised quartet scores and higher average support compared to trees inferred only from exon data. Presumably paralogous loci are often filtered out prior to species tree estimation but we find that they may contribute important phylogenetic information when using an inference method that actively accounts for them.