Prebiotics are selectively fermentable dietary compounds that result in changes in the composition and/or activity of the intestinal microbiota, thus conferring benefits upon host health. In veterinary medicine, commercially available products containing prebiotics have not been well studied with regard to the changes they trigger on the composition of the gut microbiota. This study evaluated the effect of a commercially available nutraceutical containing fructo-oligosaccharides (FOS) and inulin on the fecal microbiota of healthy cats and dogs when administered for 16 days. Fecal samples were collected at two time points before and at two time points during prebiotic administration. Total genomic DNA was obtained from fecal samples and 454-pyrosequencing was used for 16S rRNA gene bacterial profiling. The linear discriminant analysis (LDA) effect size (LEfSe) method was used for detecting bacterial taxa that may respond (i.e., increase or decrease in its relative abundance) to prebiotic administration. Prebiotic administration was associated with a good acceptance and no side effects (e.g., diarrhea) were reported by the owners. A low dose of prebiotics (50 mL total regardless of body weight with the end product containing 0.45% of prebiotics) revealed a lower abundance of Gammaproteobacteria and a higher abundance of Veillonellaceae during prebiotic administration in cats, while Staphylococcaceae showed a higher abundance during prebiotic administration in dogs. These differences were not sufficient to separate bacterial communities as shown by analysis of weighted UniFrac distance metrics. A predictive approach of the fecal bacterial metagenome using Phylogenetic Investigation of Communities by Reconstruction of Unobserved States (PICRUSt) also did not reveal differences between the period before and during prebiotic administration. A second trial using a higher dose of prebiotics (3.2 mL/kg body weight with the end product containing 3.1% of prebiotics) was tested in dogs and revealed a lower abundance of Dorea (family Clostridiaceae) and a higher abundance of Megamonas and other (unknown) members of Veillonellaceae during prebiotic administration. Again, these changes were not sufficient to separate bacterial communities or predicted metabolic profiles according to treatment. A closer analysis of bacterial communities at all time-points revealed highly individualized patterns of variation. This study shows a high interindividual variation of fecal bacterial communities from pet cats and dogs, that these communities are relatively stable over time, and that some of this variation can be attributable to prebiotic administration, a phenomenon that may be affected by the amount of the prebiotic administered in the formulation. This study also provides insights into the response of gut bacterial communities in pet cats and dogs during administration of commercially available products containing prebiotics. More studies are needed to explore potentially beneficial effects on host health beyond changes in bacterial communities.