The Utsat people do not belong to one of the recognized ethnic groups in Hainan, China. Some historical literature and linguistic classification confirm a close cultural relationship between the Utsat and Cham people; however, the genetic relationship between these two populations is not known. In the present study, we typed paternal Y chromosome and maternal mitochondrial (mt) DNA markers in 102 Utsat people to gain a better understanding of the genetic history of this population. High frequencies of the Y chromosome haplogroup O1a*-M119 and mtDNA lineages D4, F2a, F1b, F1a1, B5a, M8a, M*, D5, and B4a exhibit a pattern similar to that seen in neighboring indigenous populations. Cluster analyses (principal component analyses and networks) of the Utsat, Cham, and other ethnic groups in East Asia indicate that the Utsat are much closer to the Hainan indigenous ethnic groups than to the Cham and other mainland southeast Asian populations. These findings suggest that the origins of the Utsat likely involved massive assimilation of indigenous ethnic groups. During the assimilation process, the language of Utsat has been structurally changed to a tonal language; however, their Islamic beliefs may have helped to keep their culture and self-identification.