Background Venous thromboembolism (VTE) is a complex multifactorial disease influenced by genetic and environmental risk factors. An example for the latter is the regular use of combined oral contraceptives (CC), which increases the risk to develop VTE by 3 to 7 fold, depending on estrogen dosage and the type of progestin present in the pill. One out of 1'000 women using CC develops thrombosis, often with life-long consequences; a risk assessment is therefore necessary prior to such treatment. Currently known clinical risk factors associated with VTE development in general are routinely checked by medical doctors, however they are far from being sufficient for risk prediction, even when combined with genetic tests for Factor V Leiden and Factor II G20210A variants. Thus, clinical and notably genetic risk factors specific to the development of thrombosis associated with the use of CC in particular should be identified. Methods and findings Step-wise (logistic) model selection was applied to a population of 1622 women using CC, half of whom (794) had developed a thromboembolic event while using contraceptives. 46 polymorphisms and clinical parameters were tested in the model selection and a specific combination of 4 clinical risk factors and 9 polymorphisms were identified. Among the 9 polymorphisms, there are two novel genetic polymorphisms (rs1799853 and rs4379368) that had not been previously associated with the development of thromboembolic event. This new prediction model outperforms (AUC 0.71, 95% CI 0.69-0.74) previously published models for general thromboembolic events in a cross-validation setting. Further validation in independent populations should be envisaged. Conclusion We identified two new genetic variants associated to VTE development, as well as a robust prediction model to assess the risk of thrombosis for women using combined oral contraceptives. This model outperforms current medical practice as well as previously published models and is the first model specific to CC use.