© 2015 Mary Ann Liebert, Inc. HIV-related stigma undermines HIV prevention, testing, and treatment. Multipronged risk-reduction strategies may reduce stigma among African American adolescents. To test the effectiveness of a risk-reduction strategy in addressing stigma, 1613 African American adolescents from four mid-sized cities participated in a randomized control trial. Participants received a sexual-risk reduction [Focus on Youth (FOY)] or general health curriculum [Promoting Health Among Teens (PHAT)]. Two cities received a culturally-tailored media intervention. Participants completed baseline, 3-, 6-, and 12-month surveys to measure HIV-related stigma and knowledge. Analysis of covariance tested for stigma and knowledge differences by media city status and curriculum/media city status (PHAT media vs. PHAT non-media, FOY media vs. FOY non-media; FOY media vs. PHAT media; FOY non-media vs. PHAT non-media) at each measurement. Hierarchical linear modeling (HLM) determined stigma and knowledge differences over time. Media participants demonstrated greater HIV-related knowledge (p<0.10) at 6 months and lower stigma at 3 months (p<0.10). FOY media participants had lower 3-month (p<0.05) and 12-month (p<0.10) stigma scores than non-media FOY participants. FOY media and non-media participants had greater knowledge than PHAT for all intervals after baseline. FOY media had lower stigma than PHAT media after baseline for all intervals after baseline. HLM indicated greater knowledge slopes for the media group (p<0.05). FOY media participants had greater knowledge slopes (p<0.05) relative to non-media FOY participants and media PHAT participants (p<0.01). A combination of a HIV risk-reduction curriculum and culturally-tailored media demonstrated some effectiveness in reducing stigma. Future use of media in HIV-prevention should include and evaluate effects on stigma.