The phylogenetic relationships of Costaceae, a tropical monocotyledonous family sister to the gingers (Zingiberaceae), were investigated with a combination of two chloroplast loci (the trnL-F locus, including the trnL intron, the 3′trnL exon, and the trnL-F intergenic spacer, and the trnK locus, including the trnK intron and the matK coding region) and one nuclear locus (ITS1–5.8s–ITS2). The resulting parsimony analysis of selected taxa that demonstrate the range of floral morphological variation in the family shows that the Caldavena-type floral morphology is ancestral to the group and that both Tapeinochilos species and a Monocostus + Dimerocostus clade represent recent divergences. The genus Costus is broadly paraphyletic but Costus subgenus Eucostus K. Schum. represents a large monophyletic radiation that is poorly resolved. Within this clade, secondary analyses suggest that pollination syndrome, traditionally used for taxonomic and classification purposes within the genus Costus, is a relatively plastic trait of limited phylogenetic utility. This represents the first detailed investigation into intrageneric and interspecific evolutionary relationships within the family Costaceae and presents some novel evolutionary trends with respect to floral morphology and biogeography.