The gut microbiota is hypothesized to have a critical role in metabolic diseases, including type 2 diabetes (T2D). A traditional Chinese herbal formula, Gegen Qinlian Decoction (GQD), can alleviate T2D. To find out whether GQD modulates the composition of the gut microbiota during T2D treatment, 187 T2D patients were randomly allocated to receive high (HD, n=44), moderate (MD, n=52), low dose GQD (LD, n=50) or the placebo (n=41) for 12 weeks in a double-blinded trial. Patients who received the HD or MD demonstrated significant reductions in adjusted mean changes from baseline of fasting blood glucose (FBG) and glycated hemoglobin (HbA1c) compared with the placebo and LD groups. Pyrosequencing of the V3 regions of 16S rRNA genes revealed a dose-dependent deviation of gut microbiota in response to GQD treatment. This deviation occurred before significant improvement of T2D symptoms was observed. Redundancy analysis identified 47 GQD-enriched species level phylotypes, 17 of which were negatively correlated with FBG and 9 with HbA1c. Real-time quantitative PCR confirmed that GQD significantly enriched Faecalibacterium prausnitzii, which was negatively correlated with FBG, HbA1c and 2-h postprandial blood glucose levels and positively correlated with homeostasis model assessment of β-cell function. Therefore, these data indicate that structural changes of gut microbiota are induced by Chinese herbal formula GQD. Specifically, GQD treatment may enrich the amounts of beneficial bacteria, such as Faecalibacterium spp. In conclusion, changes in the gut microbiota are associated with the anti-diabetic effects of GQD.