This paper is a follow-up of earlier findings by the Kagera AIDS Research Project (KARP), which documented declining trends in the prevalence and incidence of HIV infection in the Kagera region of Tanzania. The paper examines socio-cultural and sexual behavioral changes as possible determinants of the observed declining trends in Bukoba, the largest urban area of the region. The study used in-depth interviews, focus group discussions, field observations and ethnographic assessments to collect the required data. The findings suggest that since the initial years of the epidemic there have been significant changes in sexual behaviors, norms, values, and customs that are considered high-risk for HIV transmission. The findings show an increase in condom use, abstinence, zero grazing (sticking to one sexual partner) and uptake of voluntary HIV testing while traditional practices such as polygamy, widow inheritance, excessive alcohol consumption, and sexual networking are declining. We suggest that these changes are partly a result of the severity of the epidemic itself in the study area, and interventions that have been carried out in this area since 1987. The major interventions have included health education, the distribution of condoms, AIDS education in schools, voluntary HIV counseling and testing. These are encouraging findings that give hope and we believe that other places within Tanzania and other countries experiencing a severe AIDS crisis have much to learn from this experience. However, changes in norms and behavior are vulnerable; people in Kagera are still at risk and there is a need for continued intervention together with monitoring of the direction of the epidemic.