Incarceration is associated with sexually transmitted infections (STIs) including human immunodeficiency virus (HIV). Incarceration may contribute to STI/HIV by disrupting primary intimate relationships that protect against high-risk relationships. Research on sexual network disruption during incarceration and implications for post-release sexual risk behavior is limited. We interviewed a sample of HIV-positive men incarcerated in North Carolina to assess how commonly inmates leave partners behind in the community; characteristics of the relationships; and the prevalence of relationship dissolution during incarceration. Among prison inmates, 52% reported having a primary intimate partner at the time of incarceration. In the period prior to incarceration, 85% of men in relationships lived with and 52% shared finances with their partners. In adjusted analyses, men who did not have a primary cohabiting partner at the time of incarceration, versus those did, appeared to have higher levels of multiple partnerships (adjusted prevalence ratio (PR), 1.5; 95% confidence interval (CI) 0.9-2.6; p = 0.11) and sex trade, defined as giving or receiving sex for money, goods, or services (adjusted PR, 2.1; 95% CI 0.9-4.8; p = 0.08) in the 6 months prior to incarceration. Involvement in financially interdependent partnerships appeared to be associated with further reductions in risk behaviors. Of men in primary partnerships at the time of prison entry, 55% reported their relationship had ended during the incarceration. The findings suggest that involvement in primary partnerships may contribute to reductions in sexual risk-taking among men involved in the criminal justice system but that many partnerships end during incarceration. These findings point to the need for longitudinal research into the effects of incarceration-related sexual network disruption on post-release HIV transmission risk.