Dysbalance in gut microbiota has been linked to increased microbial translocation, leading to chronic inflammation in HIV-patients, even under effective HAART. Moreover, microbial translocation is associated with insufficient reconstitution of CD4+T cells, and contributes to the pathogenesis of immunologic non-response. In a double-blind, randomised, placebo-controlled trial, we recently showed that, compared to placebo, 12 weeks treatment with probiotic Saccharomyces boulardii significantly reduced plasma levels of bacterial translocation (Lipopolysaccharide-binding protein or LBP) and systemic inflammation (IL-6) in 44 HIV virologically suppressed patients, half of whom (n = 22) had immunologic non-response to antiretroviral therapy (<270 CD4+Tcells/μL despite long-term suppressed viral load). The aim of the present study was to investigate if this beneficial effect of the probiotic Saccharomyces boulardii is due to modified gut microbiome composition, with a decrease of some species associated with higher systemic levels of microbial translocation and inflammation. In this study, we used 16S rDNA gene amplification and parallel sequencing to analyze the probiotic impact on the composition of the gut microbiome (faecal samples) in these 44 patients randomized to receive oral supplementation with probiotic or placebo for 12 weeks. Compared to the placebo group, in individuals treated with probiotic we observed lower concentrations of some gut species, such as those of the Clostridiaceae family, which were correlated with systemic levels of bacterial translocation and inflammation markers. In a sub-study of these patients, we observed significantly higher parameters of microbial translocation (LBP, soluble CD14) and systemic inflammation in immunologic non-responders than in immunologic responders, which was correlated with a relative abundance of specific gut bacterial groups (Lachnospiraceae genus and Proteobacteria). Thus, in this work, we propose a new therapeutic strategy using the probiotic yeast S. boulardii to modify gut microbiome composition. Identifying pro-inflammatory species in the gut microbiome could also be a useful new marker of poor immune response and a new therapeutic target.