Adolescent girls in sub-Saharan Africa are disproportionately affected by HIV/AIDS compared to boys of the same age. Few programs on the continent have sought to address the social exclusion of most marginalized girls in the poorest communities, including child domestic workers and migrants, as well as their vulnerability to HIV. Moreover, few interventions have been rigorously evaluated. “Biruh Tesfa” (Bright Future) program is for poorest adolescent girls in urban Ethiopia and aims to build their social support and improve skills to prevent HIV infection. The project uses a combination of house-to-house recruitment, formation of girls’ groups by female mentors, and education on HIV/AIDS, life skills, and basic literacy. A quasi-experimental research design involving pre- and post-intervention surveys in experimental and control areas was used to measure changes in social safety nets, HIV knowledge, and prevention capabilities. Descriptive and multivariate analyses were conducted. At endline, girls in the intervention sites were more than twice as likely to report social support (odds ratio (OR) = 2.0) compared to girls in the control site. They were also twice as likely (OR = 1.9) to score highly on HIV knowledge questions, to know where to obtain voluntary counseling and testing (OR = 2.0) and to want to be tested (OR = 1.9). “Biruh Tesfa” is one of a few rigorously evaluated support programs targeted at vulnerable girls in sub-Saharan Africa. The positive changes suggest that well-designed programs can reach and effectively support the most vulnerable girls in the poorest areas, such as child domestic workers and rural-urban migrants.