This paper examines the effect of orphanhood and HIV status of adults in a household on onset of sexual activity among adolescent girls and boys aged 15-17 years in sub-Saharan Africa (SSA). We apply multilevel logistic models to pooled Demographic and Health Surveys data from19 countries of SSA where HIV test data were collected during 2003-2008 from nationally representative samples of men and women of reproductive age. The results highlight increased vulnerability among adolescent boys and girls living in households where an adult is infected with HIV, and adolescent boys who are paternal orphans. On average, adolescent boys and girls living in households where at least one adult is HIV-positive have about 25 percent higher odds of having initiated sexual activity compared to their counterparts of similar characteristics in households where no adult is HIV-positive. Furthermore, adolescent boys who are paternal orphans have about 25 percent higher odds of having initiated sexual activity than their non-orphan counterparts of similar individual characteristics. Further analysis reveals that household circumstances relating to living arrangements and poverty are important pathways through which household HIV/AIDS status is linked to adolescent sexual debut. The findings underscore the importance of international efforts in the SSA region to address the plight of other children in HIV/AIDS affected households, beyond orphans.