The purpose of this study was to: (a) identify risk behaviors that expose Rwandan young heads of household (YHH) to HIV infection, (b) determine gender-specific high-risk profiles and, (c) determine predictors of sexual onset. A household survey was conducted among 692 YHH, ages 12–24, all beneficiaries of a World Vision basic needs program in Gikongoro, Rwanda, from January to March 2004. Participants were interviewed using a structured questionnaire. Data were collected on socio-demographic variables, knowledge about HIV/AIDS prevention and sexual risk behaviors. Bivariate analyses of the study variables were performed to examine differences between males and females. A logistic regression analysis was conducted to analyze factors that were independently associated with the debut of having sex. Forty-one percent of respondents reported sexual onset before age 15. Males were more likely to start earlier than females (50.4% versus 26.7%), but females reported more sexual onset with an older partner. Fifty-eight percent of females had their first intercourse with a partner who was four or more years older than themselves. While sexual activity was low (1.75 mean lifetime sexual partner, 0.45 mean sexual partner last 12 months), sexual experience was related to less social connectedness and use of drugs. Having a close friend also appeared to be protective for sexual debut. The analysis also found that although YHH were aware of some prevention measures against HIV/AIDS, there was low (19.8%) knowledge of the "ABC" prevention program promoted by the government. In addition, despite 85% of respondents knowing someone who had died of AIDS, only 31% perceived themselves at risk of HIV infection, and there was very low (13.2%) condom use among the sexually experienced.