Anopheles sinensis (Diptera: Culicidae) is an important malarial vector in Yunnan Province, China. In order to explore the genetic variation and population structure among different populations of the species, we sequenced and analyzed mitochondrial COII sequences of 89 An. sinensis samples. These samples were collected from nine localities in Yunnan, and were classified into five population groups based in different geographical locations. The results showed that An. sinensis had high genetic diversity in Yunnan with the haplotype diversity (h) and nucleotide diversity (π) being 0.933 and 0.00406, respectively. Fifty-one variations were found, occupying 6.9% of the total 739 bp of the COII sequence. Thirty-nine haplotypes were identified, making up 43.8% of 89 samples, with H1 and H9 being the most widespread, occupying 20.2% and 12.4% of the total haplotypes, respectively. The Jinghong-Mengla population group (JM) has the highest haplotype and genetic diversity, followed by the Yunlong population group (YL). The tropical rainforest region in Xishuangbanna, which is characterized by high temperature, humidity, and a primary ecological environment, might contribute the most to the high genetic diversity of the JM. Phylogenetic analysis did not reveal a significant relationship between the haplotypes and geographical locations. The haplotype network diagram did not reveal a relative geographical pattern of haplotype distribution, with the exception of the Yuanjiang-Yuanyang population group (YU) of haplotypes that showed obvious characteristics associated with regional distribution. Haplotypes were mainly distributed around the haplotypes H1, H9, H4, H33, and H2. Analysis of molecular variance (AMOVA) indicated the existence of population structure among population groups. No obvious Fst and Nm values were observed among four population groups (ZYT, YL, SJ, and JM) from seven sampling localities, which might indicate that there are no obvious genetic differences and that gene flow has occurred among these four population groups. However, the population group YU lacked any significant genetic exchange with other populations leading to clear genetic differentiation. For the former, this might result from the wide distribution of paddy fields, which is the predominant habitat of An. sinensis. For the latter, the Mountain Ailaoshan barrier, a region with a unique geography and climate, might result in genetic separation. Yuanjiang and Yuanyang for YU are located north-south from Mountain Ailaoshan so that the group separated from the other four groups into two different climate environments. Mismatch distribution was unimodal and the Neutral Test values were significantly negative. These might indicate that a complicated population expansion occurred in the An. sinensis populations in Yunnan. The high percentage of haplotypes and low percentage of nucleotide diversity also supports the recent population expansion of the species in Yunnan. The population expansion might be relative to the geological changes in Yunnan, especially in the period from the late Proterozoic sinian to the Mesozoic cretaceous. During this period, Yunnan experienced a number of crustal movements, and some groups of mosquitoes survived following the changes, and adapted and expanded into new environments. This study provides information about genetic diversity and population characteristics, and is of importance for the control of An. sinensis and malaria in Yunnan.