The relative contribution of novel fibers such as polydextrose and soluble corn fiber (SCF) to the human gut microbiome and its association with host physiology has not been well studied. This study was conducted to test the impact of polydextrose and SCF on the composition of the human gut microbiota using 454 pyrosequencing and to identify associations among fecal microbiota and fermentative end-products. Healthy adult men (n = 20) with a mean dietary fiber (DF) intake of 14 g/d were enrolled in a randomized, double-blind, placebo-controlled crossover study. Participants consumed 3 treatment snack bars/d during each 21-d period that contained no supplemental fiber (NFC), polydextrose (PDX; 21 g/d), or SCF (21 g/d) for 21 d. There were no washout periods. Fecal samples were collected on d 16-21 of each period; DNA was extracted, followed by amplification of the V4-V6 region of the 16S rRNA gene using barcoded primers. PDX and SCF significantly affected the relative abundance of bacteria at the class, genus, and species level. The consumption of PDX and SCF led to greater fecal Clostridiaceae and Veillonellaceae and lower Eubacteriaceae compared with a NFC. The abundance of Faecalibacterium, Phascolarctobacterium, and Dialister was greater (P < 0.05) in response to PDX and SCF intake, whereas Lactobacillus was greater (P < 0.05) only after SCF intake. Faecalibacterium prausnitzii, well known for its antiinflammatory properties, was greater (P < 0.05) after fiber consumption. Principal component analysis clearly indicated a distinct clustering of individuals consuming supplemental fibers. Our data demonstrate a beneficial shift in the gut microbiome of adults consuming PDX and SCF, with potential application as prebiotics.