This study was designed to analyze the influence of polymorphisms in CYP2C9, VKORC1, CYP4F2, GGCX, and EPHX1 genes on the optimal warfarin dosage in patients who have undergone artificial heart valve replacement and establish an algorithm for use by physicians in Southeast China to predict each patient’s optimal steady-state warfarin dose. One-hundred and ninety-six patients scheduled for heart valve replacement in Southeast China were enrolled in this study. Five genotypes, CYP2C9, VKORC1, CYP4F2, GGCX and EPHX1, were detected using time-of-flight mass spectrometry. Correlations of clinical and genetic factors with optimal steady-state dose of warfarin were analyzed. There were significant correlations between the genotypes of CY2C9, VKORC1, CYP4F2 and the warfarin dosage (P = 0.000, 0.000 and 0.015). Multiple stepwise regression analysis was performed to obtain the following algorithm: [Dose (mg/day) = EXP(0.540 + 0.544 × VKORC1 - 0.392 × CYP2C9 + 0.342 × CYP4F2 + 0.474 × BSA - 0.005 × Age)]. This algorithm could predict 49.2% of the observed differences in optimal warfarin dosage among the enrolled patients. A retrospective validation study comparing this algorithm with the published algorithms used in patient populations of other races revealed that the obtained algorithm had the best accuracy (The smallest MRE: 21.11 ± 19.08 mg/day) and applicability (the largest RE proportion of patients in ideal rang: 58.3%). This study 1) defined the relative contributions of age, body surface area, and polymorphisms in CYP2C9, VKORC1, and CYP4F2 to the optimal steady-state dosage of warfarin; 2) established a dose prediction algorithm for populations in this region that takes into account the clinical, pharmacological and genetic polymorphism data; and 3) clarified the advantages of this algorithm over the established prediction equations. Our algorithm can assist clinicians in Southeast China in prescribing appropriate anticoagulation therapy.