The montane honeybee, Apis nuluensis, is adapted to the Mt. Kinabalu highlands of Borneo. We analyzed the phylogenetic position of this bee using three mitochondrial genes, 16S ribosomal RNA(16S)and cytochrome oxidases subunit 1 and 2 (CO1 and CO2). The earlier suggestion that A. nuluensis is closely related to A. cerana was supported. We showed that this honeybee may derive from an isolated population of honeybees that colonized Borneo during Plio-Pleistocene glaciations. Based on the divergence rate for silent sites of mtDNA (2.3% per Ma), the population division between A. nuluensis and A. cerana in Borneo occurred between 0.5 Ma (from 16S) and 2.4 Ma (from CO1). Large inconsistencies in the application of CO2 in the phylogenetic analysis of Apis were found. Geographic radiation of the eastern hive bee, Apis cerana, occurred in unison with divergence, which led to the speciation of Apis nuluensis.