The health effects of a supplemented Mediterranean diet (SMD) with extra-virgin olive oil (EVOO) and nuts are well documented in non-HIV-infected individuals. We hypothesised that the benefits of an SMD could be mediated by changes in the gut microbiota, even in those with an altered intestinal microbiota such as people living with HIV. Individuals living with HIV (n = 102) were randomised to receive an SMD with 50 g/day of EVOO and 30 g/day of walnuts (SMD group) or continue with their regular diet (control group) for 12 weeks. Adherence to the Mediterranean diet was assessed using the validated 14-item MD-Adherence-Screener (MEDAS) from the PREDIMED study. A sub-study classifying the participants according to their MEDAS scores was performed. The lipid profile was improved in the SMD group vs. that in the control group (delta-total cholesterol and delta-B-lipoprotein). The immune activation (CD4+HLADR+CD38+ and CD8+HLADR+CD38+ cells) and IFN-γ-producing T-cells significantly decreased at week 12 compared to the baseline in the SMD group but not in the control group. The gut microbiota in those from the high-adherence group presented significantly high diversity and richness at the end of the intervention. Succinivibrio and Bifidobacterium abundances were influenced by the adherence to the MD and significantly correlated with Treg cells. The Mediterranean diet improved metabolic parameters, immune activation, Treg function, and the gut microbiota composition in HIV-1-infected individuals. Further, Mediterranean diet increased the Bifidobacterium abundances after the intervention, and it was associated to a beneficial profile.