Probiotics are believed to help to maintain a healthy balance of the human gut microbiota. Lactobacillus casei Zhang (LcZ) is a novel potential probiotic isolated from the naturally fermented food koumiss. To better understand the impact of this potential probiotic on human intestinal microbiota, 24 subjects were randomly recruited for a longitudinal study: the subjects were required to consume LcZ for 28 days, and faecal samples were collected prior to, during and after the LcZ consumption phase. Alterations in the gut microbiota were monitored using 454 pyrosequencing and quantitative polymerase chain reaction (q-PCR) technologies. We found that the consumption of LcZ significantly altered the composition of intestinal microbiota (P < 0.001) and the gut microbiota diversity. Further analysis at the genus level revealed a positive correlation between LcZ and Prevotella, Lactobacillus, Faecalibacterium, Propionibacterium, Bifidobacterium and an unidentified genus from Bacteroidaceae and Lachnospiraceae and a negative correlation between LcZ administration and the presence of Clostridium, Phascolarctobacterium, Serratia, Enterococcus, Shigella and Shewanella. Furthermore, these changes were confirmed by q-PCR data.