Background: Alterations in the composition of gut microbiota - known as dysbiosis - has been proposed to contribute to the development of obesity, thereby supporting the potential interest of nutrients targeting the gut with beneficial effect for host adiposity. We test the ability of a specific concentrate of water-extractable high molecular weight arabinoxylans (AX) from wheat to modulate both the gut microbiota and lipid metabolism in high-fat (HF) diet-induced obese mice. Methodology/Principal Findings: Mice were fed either a control diet (CT) or a HF diet, or a HF diet supplemented with AX (10% w/w) during 4 weeks. AX supplementation restored the number of bacteria that were decreased upon HF feeding, i.e. Bacteroides-Prevotella spp. and Roseburia spp. Importantly, AX treatment markedly increased caecal bifidobacteria content, in particular Bifidobacterium animalis lactis. This effect was accompanied by improvement of gut barrier function and by a lower circulating inflammatory marker. Interestingly, rumenic acid (C18:2 c9,t11) was increased in white adipose tissue due to AX treatment, suggesting the influence of gut bacterial metabolism on host tissue. In parallel, AX treatment decreased adipocyte size and HF diet-induced expression of genes mediating differentiation, fatty acid uptake, fatty acid oxidation and inflammation, and decreased a key lipogenic enzyme activity in the subcutaneous adipose tissue. Furthermore, AX treatment significantly decreased HF-induced adiposity, body weight gain, serum and hepatic cholesterol accumulation and insulin resistance. Correlation analysis reveals that Roseburia spp. and Bacteroides/Prevotella levels inversely correlate with these host metabolic parameters. Conclusions/Significance: Supplementation of a concentrate of water-extractable high molecular weight AX in the diet counteracted HF-induced gut dysbiosis together with an improvement of obesity and lipid-lowering effects. We postulate that hypocholesterolemic, anti-inflammatory and anti-obesity effects are related to changes in gut microbiota. These data support a role for wheat AX as interesting nutrients with prebiotic properties related to obesity prevention.