Abstract Background Elucidating gut microbiota among gallstone patients as well as the complex bacterial colonization of cholesterol gallstones may help in both the prediction and subsequent lowered risk of cholelithiasis. To this end, we studied the composition of bacterial communities of gut, bile, and gallstones from 29 gallstone patients as well as the gut of 38 normal individuals, examining and analyzing some 299, 217 bacterial 16S rRNA gene sequences from 120 samples. Results First, as compared with normal individuals, in gallstone patients there were significant (P < 0.001) increases of gut bacterial phylum Proteobacteria and decreases of three gut bacterial genera, Faecalibacterium, Lachnospira, and Roseburia. Second, about 70% of gut bacterial operational taxonomic units (OTUs) from gallstone patients were detectable in the biliary tract and bacteria diversity of biliary tract was significantly (P < 0.001) higher than that of gut. Third, analysis of the biliary tract core microbiome (represented by 106 bacteria OTUs) among gallstone patients showed that 33.96% (36/106) of constituents can be matched to known bacterial species (15 of which have publicly available genomes). A genome-wide search of MDR, BSH, bG, and phL genes purpotedly associated with the formation of cholesterol gallstones showed that all 15 species with known genomes (e.g., Propionibacterium acnes, Bacteroides vulgates, and Pseudomonas putida) contained at least contained one of the four genes. This finding could potentially provide underlying information needed to explain the association between biliary tract microbiota and the formation of cholesterol gallstones. Conclusions To the best of our knowledge, this is the first study to discover gut microbiota dysbiosis among gallstone patients, the presence of which may be a key contributor to the complex bacteria community assembly linked with the presence of cholesterol gallstones. Likewise, this study also provides the first large-scale glimpse of biliary tract microbiota potentially associated with cholesterol gallstones. Such a characterization of the biliary tract core microbiome has potentially important biological and medical implications regarding the role of bacteria in the formation cholesterol gallstones.