To test the hypothesis that micronutrient supplementation decreases genital HIV-1 shedding, a double-blind, randomized, placebo-controlled trial of 6 weeks of multivitamin plus selenium supplementation vs. placebo was conducted among 400 HIV-1-seropositive, nonpregnant, antiretroviral-naive women in Mombasa, Kenya. Primary outcome measures included cervical and vaginal shedding of HIV-1-infected cells and RNA. Secondary outcomes included plasma viral load and CD4 count. Surprisingly, the odds of detection of vaginal HIV-1-infected cells were 2.5-fold higher (P = 0.001) and the quantity of HIV-1 RNA in vaginal secretions was 0.37 log10 copies/swab higher (P = 0.004) among women who received micronutrients in comparison to placebo, even after adjustment for potential confounders including baseline HIV-1 shedding and CD4 count. The increase in vaginal HIV-1 shedding was greatest among women who had normal baseline selenium levels. Micronutrient supplementation resulted in higher CD4 (+23 cells/microL, P = 0.03) and CD8 (+74 cells/microL, P = 0.005) counts compared with placebo but did not alter the plasma viral load. In this randomized trial, micronutrients resulted in higher levels of genital HIV-1 shedding compared with placebo. The potential benefit of micronutrient supplementation in HIV-1-seropositive women should be considered in relation to the potential for increased infectivity.