Background: Circulating concentrations of heme oxygenase-1 (HO-1) have been recently reported to be elevated in several chronic disorders. However, no study has ever examined the association between circulating HO-1 concentrations and type 2 diabetes mellitus (T2DM). Methods and Findings: 581 cases with newly-diagnosed T2DM (New-T2DM) and 611 comparison controls were recruited in this two-phase case-control study, comprising 420 cases and 429 controls collected in the first phase study and 161 cases and 182 controls in the second phase replication study. Analyses, using both separated data and combined data from the two-phase studies, show that plasma HO-1 concentrations were significantly increased in New-T2DM cases compared to controls (P < 0.001). Plasma HO-1 concentrations were significantly correlated with plasma glucose concentrations, HOMA-beta and HOMA-IR (P < 0.001). After adjustment for age, sex, BMI and family history of diabetes, the ORs for New-T2DM in the highest quartile of plasma HO-1 concentrations, compared with the lowest, was 8.23 (95% CI 5.55-12.21; P for trend <0.001). The trend remained significant after additional adjustment for fasting plasma glucose/insulin, HOMA-beta/HOMAIR, TC/TG, smoking, drinking and history of hypertension, and even in further stratification analysis by age, sex, BMI, smoking, drinking and history of hypertension. Conclusions: Elevated plasma HO-1 concentrations are associated with higher ORs for New-T2DM, which add more knowledge regarding the important role of oxidative stress in T2DM. More consequent studies were warranted to confirm the clinical utility of plasma HO-1, especially in diagnosis and prognosis of T2DM and its complications.