The proboscis monkey, Nasalis larvatus, is an endemic species to the island of Borneo. It is listed in the IUCN Red List as Endangered with a decreasing population trend. Nevertheless, biological information, especially on the genetic diversity of the species, is still incomplete. Its fragmented distribution poses difficulties in gathering genetic samples along with its widespread distribution across Borneo. This study aims to determine the genetic variation and structure of N. larvatus with an emphasis on Malaysian Borneo populations to elucidate its gene flow. The genetic variation and structure of N. larvatus were examined using 50 sequences of the 1,434-bp cytochrome oxidase subunit I (COI) gene region of mitochondrial DNA. The COI sequences revealed low genetic variation among N. larvatus populations in Malaysian Borneo. This low genetic variability could be the result of inbreeding pressure that may have occurred due to the absence of population expansion in this species over the last 30,000 years. This is supported in our analysis of molecular variance, which showed that groups of N. larvatus are significantly differentiated possibly due to natural geographic barriers. This study provides baseline information on the genetic diversity among proboscis monkey populations in Borneo for the future genetic assessment of the species.