Background: Micronutrient deficiencies occur early in human immunodeficiency virus (HIV) infection and are associated with accelerated disease progression. We aimed to determine if long-term selenium supplementation is effective and safe in delaying CD4 T-cell decline and disease progression when implemented early in adults infected with HIV who are antiretroviral therapy (ART) naive in Rwanda. Methodology: We randomized patients in a multi-centre, patient and provider-blinded, randomized, placebo-controlled clinical trial involving ART naïve HIV-infected patients. We recruited patients ≥ 21 years of age with documented HIV infection and CD4 cell count of 400-650 cells/mm3, and not yet on ART. Patients received selenium 200 mcg per day or matching placebo. The primary outcome is change in CD4 T-cell status between groups. Secondary outcomes include a composite of CD4 depletion to 350 cells/, or start of ART, or the emergence of a documented CDC-defined AIDS-defining illness; viral suppression; mortality; and adverse events. We applied an intent-to-treat analysis. Linear regressions with generalized estimating equations and effect modification was used for the primary outcome. Results: 151 patients received selenium and 149 placebo arm, with an average baseline CD4 of 555 cells/mm3. Seventeen patients were lost to follow-up. One non-AIDS death occurred in each group. Twenty-three women were time censored due to pregnancy and placed on ART. The rate of CD4 depletion was reduced by 43.8% among patients receiving selenium (95% confidence interval [CI]: 7.8-79.8% reduced). Figure 1 displays the CD4 change over 24 months. Average declines in CD4 over the trial period were 54 cells among the selenium arm and 95 cells among the placebo arm. In total, 96 events for the composite outcome were observed, with 45 (47%) in the treatment arm. We found no treatment effect for the composite outcome (hazard ratio 1.00, 95% confidence intervals [CIs] 0.66 – 1.54) or viral suppression (odds ratio, 1.18, 95% CI 0.71 – 1.94). We found no significant differences between groups for adverse events. Conclusions: In ART-naive HIV-infected adults, 24-month selenium supplementation was safe and significantly decreased the rate of measured immune decline. Selenium supplementation may be an inexpensive and effective intervention when started in the early stages of HIV disease.