Recent interest in the gut-brain-axis has highlighted the potential of prebiotics to impact wellbeing, and to affect behavioral change in humans. In this clinical trial, we examined the impact of four-weeks daily supplementation of galacto-oligosaccharides (GOS) on self-reported nutrient intake and relationships on gut microbiota in a four-week two-armed parallel double-blind placebo controlled GOS supplement trial in young adult females. Food diaries and stool samples were collected prior to and following 28 days of supplement consumption. It was found that four weeks of GOS supplementation influenced macronutrient intake, as evident by reduced carbohydrate and sugars and increased fats intake. Further analysis showed that the reduction in carbohydrates was predicted by increasing abundances of Bifidobacterium in the GOS group in comparison to the placebo group. This suggests that Bifidobacterium increase via GOS supplementation may help improve the gut microbiota composition by altering the desire for specific types of carbohydrates and boosting Bifidobacterium availability when fiber intake is below recommended levels, without compromising appetite for fiber from food.