The papilionoid legume tribe Brongniartieae comprises a collection of 15 genera with disparate morphologies that were previously positioned in at least four remotely related tribes. The Brongniartieae displays a wide geographical disjunction between Australia and the New World and previous phylogenetic studies had provided conflicting results about the relationships between the American and Australian genera. We carry out phylogenetic analyses of (1) a plastid matK dataset extensively sampled across legumes to solve the enigmatic relationship of the Cuban-endemic monospecific genus Behaimia; and (2) multilocus datasets with focus on all genera ever referred to Brongniartieae. These analyses resulted in a well-resolved and strongly-supported phylogenetic tree of the Brongniartieae. The monophyly of all American genera of Brongniartieae is strongly supported. The doubtful position of the Australian genus Plagiocarpus is resolved within a clade comprising all Australian genera. Behaimia has been traditionally classified in tribe Millettieae, but our new molecular data and re-assessment of morphological traits have resolved the genus within the early-branching papilionoid tribe Brongniartieae. Characters including the pinnately multifoliolate (vs. unifoliolate) leaves, a sessile (vs. stipitate) ovary, and an indehiscent or late dehiscent one-seeded pod distinguish Behaimia from its closer relatives, the South American genera Cyclolobium and Limadendron.