Xinjiang has large sheep breeds, but their origins, evolution, genetic diversity of systems are still unclear. In this study, the genetic diversity and phylogeny of 19 indigenous sheep breeds in Xinjiang, China and one western breed, Texel were analyzed. Single-strand conformation polymorphism (SSCP) was used to detect polymorphisms of the sheep mitochondrial DNA fragment and based on SSCP results, individuals from the studied sheep breeds were randomly selected for sequencing entire Cytochrome b gene (Cyt b). Neighbor joining (NJ) and Unweighted Pair Group Method with Arithmetic Averaging (UPGMA) methods were used to constructing the phylogenetic tree. The network analysis and population expansion were carried out with entire sequences of mitochondria Cyt b gene. The length of the Cyt b sequences were considerably variable between 1082 and 1149bp. The phylogenetic analysis revealed that three mtDNA lineages A, B and C were detected in fourteen Xinjiang sheep breeds, except for the absence of lineage C in five breeds. Phylogenetic tree and median joining network were constructed with the sequenced Cyt b gene, and there were three independent clusters with some sequences deviated from cluster A and C based on the phylogenetic tree and network analysis. The genetic distances were showed a multi-maternal originality of the nineteen Xinjiang local sheep breeds, which were clustered with the sheep groups in other parts of China. The genetic diversity of Xinjiang breeds was higher than the other Chinese and foreign sheep breeds. The results of Cyt b sequences analysis revealed that Xinjiang local sheep breeds may have distinct maternal origins than the other sheep breeds of China. These are not only influenced by Mongolian sheep, Tibetan sheep and Kazakh sheep of China, but also had the genetic relationship with the breeds of other neighbor countries. This study will provide valuable information of sophisticated phylogenetic history of Xinjiang local sheep.