Uganda has been hailed as a success story in the fight against HIV that has seen a reversal in prevalence from a peak of 15% in 1991 to about 6.5% currently. Since 1992, the largest and most consistent declines in HIV have occurred among the 15-19-year-olds. While many studies have examined how key behavior changes (Abstinence, Be faithful and Condom use) have contributed to the decline in HIV prevalence, few have studied the relationship between sexual behaviors and risk perception. Using data from the 2004 National Survey of Adolescents, multivariate logistic regression models were fitted to examine the strength of the association between risky sexual behavior and perceived risk among 12-19-year-old adolescents in Uganda. After controlling for other correlates of sexual behavior such as age, education, residence, region and marital status, the findings indicate highly significant positive association between perceived risk and risky sexual behavior among males but not females. The findings reveal that, regardless of their current sexual behavior, most female adolescents in Uganda feel at great risk of HIV infection. The findings also show that adolescents with broken marriages are much more vulnerable to high risk sexual behaviors than other categories of adolescents. These results further emphasize the need for a holistic approach in addressing the social, economic and contextua