We investigated the modulating effect of α-(1→3)-glucooligosaccharides (GOS), i.e. a product of fungal α-(1→3)-d-glucan hydrolysis, on the gut microbiota composition. Mice were fed with a GOS-supplemented diet and two control diets for 21 days, and fecal samples were collected at 0, 1, and 3-week time points. The bacterial community composition was determined by 16S rRNA gene Illumina sequencing. The gut microbiota of the GOS-supplemented mice showed profound time-dependent changes in the taxonomic composition; however, we did not observe significant changes in α-diversity indices. The biggest number of genus abundance shifts after 1 week of the treatment was noticed between the group of the GOS-supplemented mice and the controls; however, the differences were still relevant after the 3-week treatment. The GOS-supplemented mice displayed higher abundance of Prevotella spp., with a concomitant decrease in the abundance of Escherichia-Shigella. Hence, GOS seems to be a promising candidate for a new prebiotic.