The Udegeys are a small ethnic group who live along the tributaries of the Amur River Basin of southeastern Siberia in Russia. They are thought to speak a language belonging to a subdivision of the Tungusic-Manchu branch of the Altaic family. To understand the genetic features and genetic history of the Udegeys, we analyzed two haploid markers, mitochondrial DNA (mtDNA), and Y-chromosomal variation, in 51 individuals (including 21 males) from the Udegey population. In general, the Udegeys' mtDNA profiles revealed similarities to Siberians and other northeastern Asian populations, although a moderate European contribution was also detected. Interestingly, pairwise values of F(ST) and the MDS plots based on the mtDNA variation showed that the Orok and Nivkh inhabiting the very same region of the Udegey were significantly different from the Udegey, implying that they may have been isolated and undergone substantial genetic drift. The Udegeys were characterized by a high frequency (66.7%) of Y chromosome haplogroup C, indicating a close genetic relationship with Mongolians and Siberians. On the paternal side, however, very little admixture was observed between the Udegeys and Europeans. Thus, the combined haploid genetic markers of both mtDNA and the Y chromosome imply that the Udegeys are overall closest to Siberians and northeast Asians of the Altaic linguistic family, with a minor maternal contribution from the European part of the continent.