Background: Despite efficient antiretroviral treatment (ART) HIV-infected patients have increased morbidity and mortality compared to HIV seronegative individuals. Gut microbiota composition has potential impact on HIV pathogenesis and cardiovascular risk. Notably, markers of inflammation, coagulation and microbial translocation have been reported to predict all-cause mortality. The aim of this study was to assess the efficacy of probiotic supplementation in HIV-infected individuals. Methodology: Randomized, placebo-controlled trial, completed study. Thirty HIV-infected patients on ART (median age 50.3y, 22 men, 22 Caucasians) were included. Inclusion criteria were: HIV-RNA < 50 copies/ml, CD4 count < 500 cells/μl, no antibiotics or probiotics prescribed for the last 2 months, and no episodes of inflammatory bowel disease, immunomodulating therapy or infectious diarrhea for the last 6 months. Participants were randomized in a double blind fashion to the following study arms: i) probiotics (n=14), ii) placebo (n=8), and iii) controls (n=8). The probiotic consisted of 250 ml/ day fermented skimmed milk supplemented with Lactobacillus rhamnosus GG (108 cfu/ml), Bifidobacterium animalis subsp. lactis B12 (108 cfu/ml), and Lactobacillus acidophilus La-5 (107 cfu/ml). Heat-treated fermented skimmed milk served as placebo. The intervention period was 8 weeks. LPS was analyzed by Limulus Amebocyte Lysate colorimetric assay (LAL) (Lonza, USA), soluble (s) CD14 and IL-6 by ELISA (R&D Systems) and D-dimer was measured by Asserachrom kits (Diagnostica Stago, Asniere, France). Non-parametric statistics were applied. Results: Twenty-five completed the trial leaving 12 patients in the probiotic group, 7 placebo and 6 controls. No serious adverse events were recorded. In patients receiving probiotics, there was a 33% reduction from baseline to 8 weeks in the levels of the coagulation marker D-dimer, from a median of 320.3 ng/mL (239.8-474.7 IQR) to 214.2 ng/mL (142.0-392.6 IQR) (p=0.03, Wilcoxon). IL-6 levels decreased 13.8% from median 1.23 pg/mL (0.94-2.46 IQR) to 1.06 pg/mL (0.93-1.39 IQR) in the probiotic group (p=0.06, Wilcoxon). No changes were found in the placebo group or controls. CD4 counts, plasma LPS or soluble CD14 did not change significantly in any of the study arms. Conclusions: Probiotic supplement significantly reduced D-dimer levels and possibly also levels of IL-6, both markers related to HIV-associated inflammation and cardiovascular disease. This reduction was apparently not related to changes in markers of microbial translocation. Additional studies to further elucidate mechanisms by which probiotics can influence upon gut microbiota, coagulation and inflammation are warranted.