Background: HIV infection related to commercial sexual contact is a serious public health issue in China. The objectives of the present study are to explore the predictors of condom use among female sex workers (FSWs) in China and examine the relationship between Health Belief Model (HBM) constructs. Methodology/Principal Findings: A cross-sectional study was conducted in two cities (Wuhan and Suizhou) in Hubei Province, China, between July 2009 and June 2010. A total of 427 FSWs were recruited through mediators from the 'low-tier' entertainment establishments. Data were obtained by self-administered questionnaires. Structural equation models were constructed to examine the association. We collected 363 valid questionnaires. Within the context of HBM, perceived severity of HIV mediated through perceived benefits of condom use had a weak effect on condom use (r = 0.07). Perceived benefits and perceived barriers were proximate determinants of condom use (r = 0.23 and r = -0.62, respectively). Self-efficacy had a direct effect on perceived severity, perceived benefits, and perceived barriers, which was indirectly associated with condom use behaviors (r = 0.36). Conclusions/Significance: The HBM provides a useful framework for investigating predictors of condom use behaviors among FSWs. Future HIV prevention interventions should focus on increasing perceived benefits of condom use, reducing barriers to condoms use, and improving self-efficacy among FSWs.