The US HIV/AIDS epidemic is concentrated in the Deep South, yet factors contributing to HIV transmission are not fully understood. We examined relationships between substance use, sexual partnership characteristics, and condom non-use in an African American sample of STI clinic attendees in Jackson, Mississippi. We assessed condom non-use at last intercourse with up to three recent sexual partners reported by participants between January and June 2011. Participant- and partner-level correlates of condom non-use were examined using generalized estimating equations. The 1295 participants reported 2880 intercourse events, of which 1490 (51.7 %) involved condom non-use. Older age, lower educational attainment, reporting financial or material dependence on a sex partner, sex with a primary partner, and higher frequency of sex were associated with increased odds of condomless sex. HIV prevention efforts in the South should address underlying socioeconomic disparities and structural determinants that result in partner dependency and sexual risk behavior.