Arthrostylidiinae (Poaceae: Bambusoideae), a subtribe of Neotropical woody bamboos with diverse morphology, comprises 200 species classified in 16 genera. Previous studies supported monophyly of the subtribe and recovered four major internal clades, however, some genera were found to be polyphyletic while others, like Aulonemia and Colanthelia, were either undersampled or not included. Aulonemia and Colanthelia are complex both in their taxonomy and morphology, and exhibit overlapping morphological characters. Prior morphological and molecular analyses suggested they share a close relationship, with Colanthelia emerging as monophyletic and either nested within Aulonemia or sister to it, but these studies sampled relatively few species of each genus. The aims of this study were to increase taxon sampling to test the monophyly of Aulonemia and Colanthelia, to investigate the relationships within the Aulonemia + Colanthelia clade, and to revise their classification as appropriate towards a natural classification of the Arthrostylidiinae. We present a multi-locus plastid phylogeny of the Arthrostylidiinae with emphasis on Aulonemia and Colanthelia. We used sequences of seven plastid markers (one coding: ndhF; six non-coding: trnC-rpoB, rps16-trnQ, trnT-trnL, rps16, trnD-trnT, and rpl16) from 67 taxa of Bambusoideae including all genera of Arthrostylidiinae. Phylogenetic trees were inferred using both Bayesian and maximum likelihood methods. Aulonemia was confirmed as polyphyletic and Colanthelia was not supported as monophyletic. The phylogenetic position of Myriocladus within Arthrostylidiinae is resolved for the first time. All species of Colanthelia were recovered within the clade containing most species of Aulonemia. Four species of Aulonemia (A. radiata, A. effusa, A. setosa, and A. setigera) grouped in other clades within the subtribe and these placements combined with morphological evidence support the establishment of three new genera: Quixiume, Stelanemia and Vianaea, to accommodate the four remarkable Aulonemia species. An updated key for the genera of the Arthrostylidiinae is provided, as well as taxonomic treatments for the three new genera, including the description of a new species in Stelanemia.