The intestinal gut microbiota is important for human metabolism and immunity and can be influenced by many host factors. A recently emerged host factor is secreted microRNA (miRNA). Previously, it has been shown that secreted miRNAs can influence the growth of certain bacteria and conversely, that shifts in the microbiota can alter the composition of secreted miRNAs. Here, we sought to further investigate the interaction between the gut microbiota and secreted miRNAs by the use of fecal microbiota transplantation (FMT). Subjects with the metabolic syndrome received either an autologous (n = 4) or allogenic (n = 14) FMT. Fecal samples were collected at baseline and 6 weeks after FMT, from which the microbiome and miRNA composition were determined via 16S rRNA sequencing and miRNA sequencing, respectively. We observed a significant correlation between the fecal miRNA expression and microbiota composition, both before and after FMT. Our results suggest that the FMT-induced shift in microbiota altered the fecal miRNA profile, indicated by correlations between differentially abundant microbes and miRNAs. This idea of a shift in miRNA composition driven by changes in the microbiota was further strengthened by the absence of a direct effect of specific miRNAs on the growth of specific bacterial strains.