The paleotropical woody bamboo subtribe Bambusinae has not been satisfactorily circumscribed and remains a major taxonomic problem. Genera such as Holttumochloa, Mullerochloa and Temburongia have not been confidently assigned to this subtribe. The phylogenetic relationships among genera hitherto placed in or near the Bambusinae, together with the related subtribes Racemobambosinae and Melocanninae, were investigated using three chloroplast DNA markers (rps16-trnQ, trnC-rpoB and trnD-T intergenic spacers) and a nuclear DNA marker (granule-bound starch synthase I, GBSSI) for a sample of 51 ingroup species and 2 outgroup species. Phylogenetic analyses revealed four distinct lineages among the members of the currently recognized Bambusinae: (1) the Bambusa-Dendrocalamus-Gigantochloa (BDG) complex, (2) the Holttumochloa-Kinabaluchloa clade, (3) the Dinochloa-Mullerochloa-Neololeba-Sphaerobambos (DMNS) clade and (4) Temburongia simplex. The BDG complex, which comprises the core of the Bambusinae, appears to have a complex evolutionary history as indicated by incongruence between the cpDNA and the nuclear gene topologies. Introgressive hybridization and incomplete lineage sorting are possible underlying causes for this complexity. The distinction of the climbing-scrambling bamboo lineages from the core Bambusinae and Racemobambosinae suggests directions for investigating the possible existence of further subtribes with increased taxon and geographical sampling. Possible biogeographic scenarios associated with the Holttumochloa-Kinabaluchloa clade and the DMNS clade are discussed.