Abstract Men who have been incarcerated experience substantial changes in their sexual behavior after release from jail and prison, and high rates of incarceration may change sexual relationship patterns at a community level. Few studies, however, address how rates of incarceration affect community patterns of sexual behavior, and the implications of those patterns for HIV and STD risk. We describe a “proof of principle” computational model that tests whether rates of male incarceration could, in part, explain observed population-level differences in patterns of sexual behavior between communities with high rates of incarceration and those without. This validated agent-based model of sexual partnership among 20–25 year old heterosexual urban residents in the United States uses an algorithm that incarcerates male agents and then releases them back into the agent community. The results from these model experiments suggest that at rates of incarceration similar to those observed for urban African American men, incarceration can cause an increase in the number of partners at the community level. The results suggest that reducing incarceration and creating a more open criminal justice system that supports the maintenance of inmates' relationships to reduce instability of partnerships for men who are incarcerated may have important sexual health and public health implications. Incarceration is one of many social forces that affect sexual decision-making, and incarceration rates may have substantial effects on community-level HIV and STD risks.