There is growing evidence of the association between gender-based violence and HIV from the perspective and experiences of women. The purpose of this study is to examine these associations from the perspective of young men living in Dar es Salaam, Tanzania. A community-based sample of 951 men were interviewed, of whom 360 had sex in the past 6 months and were included in these analyses. Almost a third of the men (29.2%) reported that they had been physically violent at least once with an intimate partner. Men who reported more lifetime sexual partners (OR = 8.75; 95% CI = 2.65, 28.92), experienced physical violence as a child at home (OR = 1.73; 95% CI = 1.09, 2.76), and were more educated (OR = 1.91; 95% CI = 1.18, 3.11) were significantly more likely to report perpetrating violence. These associations persisted after adjusting for other variables. These data from the perspective of young men reinforce earlier findings from women that HIV risk and violence are occurring together in relationships of young adults. Interventions are needed to identify men at high risk for HIV and engage them in interventions that are designed to change norms and behaviors related to power and control with their sexual partners.