Altered interactions between the gut mucosa and bacteria during HIV infection seem to contribute to chronic immune dysfunction. A deeper understanding of how nutritional interventions could ameliorate gut dysbiosis is needed. Forty-four subjects, including 12 HIV+ viremic untreated (VU) patients, 23 antiretroviral therapy-treated (ART+) virally suppressed patients (15 immunological responders and 8 non-responders) and 9 HIV- controls (HIV-), were blindly randomized to receive either prebiotics (scGOS/lcFOS/glutamine) or placebo (34/10) over 6 weeks in this pilot study. We assessed fecal microbiota composition using deep 16S rRNA gene sequencing and several immunological and genetic markers involved in HIV immunopathogenesis. The short dietary supplementation attenuated HIV-associated dysbiosis, which was most apparent in VU individuals but less so in ART+ subjects, whose gut microbiota was found more resilient. This compositional shift was not observed in the placebo arm. Significantly, declines in indirect markers of bacterial translocation and T-cell activation, improvement of thymic output, and changes in butyrate production were observed. Increases in the abundance of Faecalibacterium and Lachnospira strongly correlated with moderate but significant increases of butyrate production and amelioration of the inflammatory biomarkers soluble CD14 and high-sensitivity C-reactive protein, especially among VU. Hence, the bacterial butyrate synthesis pathway holds promise as a viable target for interventions.