Few studies have been conducted on the distribution of Enterocytozoon bieneusi genotypes in Tibetan sheep and yaks, which live outdoors in extreme climate with high altitude. In this study, fecal specimens from 312 Tibetan sheep and 554 yaks in Qinghai, China, were collected and examined for E. bieneusi by PCR-sequence analysis of the ribosomal internal transcribed spacer. Among them, 73 (23.4%) specimens from Tibetan sheep and 40 (7.2%) from yaks were positive for E. bieneusi. There were eight E. bieneusi genotypes in Tibetan sheep, including three known ones (BEB6, COS-I, and NESH5) and five novel ones (named as CHS13-CHS17). Similarly, seven E. bieneusi genotypes were found in yaks, including five known ones (J, BEB4, BEB6, COS-I, and NESH5) and two novel ones (named as CHN13 and CHN14). Most of the E. bieneusi genotypes and all frequent ones identified in the study belonged to group 2. One new subgroup of genotypes was identified within group 1. The distribution of E. bieneusi genotypes was different between Tibetan sheep and yaks, with BEB6 as the dominant one (42.5%) in Tibetan sheep and J as the dominant one (47.5%) in yaks. These data support the occurrence of host adaptation among E. bieneusi genotypes within group 2.