Single-copy organelle DNA loci are widely used to infer plants’ phylogenetic relationships. In bananas (Musa spp.), the maternal transmission of chloroplast DNA and paternal transmission of mitochondrial DNA provides an excellent possibility to follow both maternal and paternal lineages by using chloroplast and mitochondrial markers, respectively. In the present study, 25 chloroplast and 12 mitochondrial DNA sequences of Musa spp. were used to elucidate the genetic diversity and phylogenetic relationships of wild and cultivated bananas. Sequence alignment and phylogenetic analyses grouped the 34 wild and 26 cultivars into different clades and subclades. The use of cytoplasmic genes to analyze the origin and evolution of cultivated bananas revealed two main maternal and paternal origins: via Musa acuminata Colla and via Musa balbisiana Colla. Relationships among wild accessions and intra- and interspecific hybrids, as well as between the latter, evidenced eight chloroplast and six mitochondrial gene pools, and 18 cytotypes were identified. The maternal origin of most M. acuminata hybrids was the Ca2 gene pool, while the A-B hybrids were derived from the Ca3 or Ca5 gene pools. The most common paternal origin was the Ma3 gene pool, except for ABB genotypes with Mb1 origin. Furthermore, we found a role for Musa itinerans Cheesman in the paternal origin of banana cultivars. The present findings will help refine Musa spp. phylogeny, and enrich the available cytoplasmic data for Musa spp. germplasms that will be useful for improving the breeding of banana cultivars.