The optimal timing of vitamin K antagonists (VKAs) resumption after an upper gastrointestinal (GI) bleeding, in patients with continued indication for oral anticoagulation, is uncertain. We included consecutive cases of VKA-associated upper GI bleeding from three hospitals retrospectively. Data on the bleeding location, timing of VKA resumption, recurrent GI bleeding and thromboembolic events were collected. A model was constructed to evaluate the ‘total risk’, based on the sum of the cumulative rates of recurrent GI bleeding and thromboembolic events, depending on the timing of VKA resumption. A total of 121 (58 %) of 207 patients with VKA-associated upper GI bleeding were restarted on anticoagulation after a median (interquartile range) of one (0.2–3.4) week after the index bleeding. Restarting VKAs was associated with a reduced risk of thromboembolism (HR 0.19; 95 % CI, 0.07–0.55) and death (HR 0.61; 95 % CI, 0.39–0.94), but with an increased risk of recurrent GI bleeding (HR 2.5; 95 % CI, 1.4–4.5). The composite risk obtained from the combined statistical model of recurrent GI bleeding, and thromboembolism decreased if VKAs were resumed after three weeks and reached a nadir at six weeks after the index GI bleeding. On this background we will discuss how the disutility of the outcomes may influence the decision regarding timing of resumption. In conclusion, the optimal timing of VKA resumption after VKA-associated upper GI bleeding appears to be between 3–6 weeks after the index bleeding event but has to take into account the degree of thromboembolic risk, patient values and preferences.