The gaur (Bos gaurus) is one of the two extant wild cattle species that can be found in several Asian countries. This species is threatened by extinction due to declining wild populations. Selembu is the name of the Malayan gaur × domestic cattle hybrid. We planned this study to determine the position of the Malayan gaur and its hybrid, the selembu, in the phylogenetics of the genus Bos (Bos gaurus, Bos javanicus, Bos indicus, and Bos taurus). The mitochondrial 12S rRNA gene and the control region (D-loop) were sequenced in 29 Bos samples. Sequences from one water buffalo (Bubalus) were used as an outgroup. Phylogenetic trees were reconstructed using neighbor-joining and maximum parsimony in PAUP 4.0b10 and Bayesian inference in MrBayes 3.1. All tree topologies indicated that the Malayan gaur belongs to its own monophyletic clade that is distinct from other species of the genus Bos. Selembu samples were grouped in zebu and/or taurine cattle clades. The results also indicated that there are significant embranchment differences in the tree topologies between wild (Malayan gaur and banteng/Bali cattle) and domestic (taurine cattle, zebu cattle, and selembu) cattle. The results showed the complete maternal inheritance situation among the studied samples of all cattle species.