The amount of data collected previously for Velloziaceae neither clarified relationships within the family nor helped determine an appropriate classification, which has led to huge discordance among treatment by different authors. To achieve an acceptable phylogenetic result and understand the evolution and roles of characters in supporting groups, a total evidence analysis was developed which included approx. 20 % of the species and all recognized genera and sections of Velloziaceae, plus outgroups representatives of related families within Pandanales. Analyses were undertaken with 48 species of Velloziaceae, representing all ten genera, with DNA sequences from the atpB-rbcL spacer, trnL-trnF spacer, trnL intron, trnH-psbA spacer, ITS ribosomal DNA spacers and morphology. Four groups consistently emerge from the analyses. Persistent leaves, two phloem strands, stem cortex divided in three regions and violet tepals support Acanthochlamys as sister to Velloziaceae s.s., which are supported mainly by leaves with marginal bundles, transfusion tracheids and inflorescence without axis. Within Velloziaceae s.s., an African Xerophyta + Talbotia clade is uniquely supported by basal loculicidal capsules; an American clade, Barbacenia s.l. + Barbaceniopsis + Nanuza + Vellozia, is supported by only homoplastic characters. Barbacenia s.l. (= Aylthonia + Barbacenia + Burlemarxia + Pleurostima) is supported by a double sheath in leaf vascular bundles and a corona; Barbaceniopsis + Nanuza + Vellozia is not supported by an unambiguous character, but Barbaceniopsis is supported by five characters, including diclinous flowers, Nanuza + Vellozia is supported mainly by horizontal stigma lobes and stem inner cortex cells with secondary walls, and Vellozia alone is supported mainly by pollen in tetrads. The results imply recognition of five genera (Acanthochlamys (Xerophyta (Barbacenia (Barbaceniopsis, Vellozia)))), solving the long-standing controversies among recent classifications of the family. They also suggest a Gondwanan origin for Velloziaceae, with a vicariant pattern of distribution.