The effects of genetic variants on warfarin dosing vary among different ethnic groups, especially in the Chinese population. The objective of this study was to recruit patients through a rigorous experimental design and to perform a comprehensive screen to identify gene polymorphisms that may influence warfarin dosing in northern Han Chinese patients with mechanical heart valve replacement. Consenting patients (n=183) with a stable warfarin dose were included in this study. Ninety-six single nucleotide polymorphisms (SNPs) in 30 genes involved in warfarin pharmacological pathways were genotyped using the Illumina SNP GoldenGate Assay, and their associations with warfarin dosing were assessed using univariate regression analysis with post hoc comparison using least significant difference analysis. Multiple linear regression was performed by incorporating patients' clinical and genetic data to create a new algorithm for warfarin dosing. From the 96 SNPs analyzed, VKORC1 rs9923231, CYP1A2 rs2069514, CYP3A4 rs28371759, and APOE rs7412 were associated with higher average warfarin maintenance doses, whereas CYP2C9 rs1057910, EPHX1 rs2260863, and CYP4F2 rs2189784 were associated with lower warfarin doses (P<0.05). Multiple linear regression analysis could estimate 44.4% of warfarin dose variability consisting of, in decreasing order, VKORC1 rs9923231 (14.2%), CYP2C9*3 (9.6%), body surface area (6.7%), CYP1A2 rs2069514 (3.7%), age (2.7%), CYP3A4 rs28371759 (2.5%), CYP4F2 rs2108622 (1.9%), APOE rs7412 (1.7%), and VKORC1 rs2884737 (1.4%). In the dosing algorithm we developed, we confirmed the strongest effects of VKORC1, CYP2C9 on warfarin dosing. In the limited sample set, we also found that novel genetic predictors (CYP1A2, CYP3A4, APOE, EPHX1, CYP4F2, and VKORC1 rs2884737) may be associated with warfarin dosing. Further validation is needed to assess our results in larger independent northern Chinese samples.