Background: Growing evidence suggests the relationship between obstructive sleep apnea (OSA) and venous thromboembolism (VTE). Few studies focused on VTE recurrence risk associated with OSA after anticoagulation cessation. Methods: In a prospective cohort study, patients with documented VTE, were followed for an indefinite length of time and VTE recurrence were documented and adjudicated. The primary outcome was recurrent VTE after anticoagulation discontinuation. Secondary outcomes included all-cause mortality and the clinical presentation of VTE. Univariable and multivariable analyses were performed to identify risk factors for recurrence and mortality. Results: Among the 2109 patients with documented VTE included, 74 patients had moderate to severe OSA diagnosis confirmed by home sleep test or polysomnography. During a median follow-up of 4.8 (interquartile range 2.5–8.0) years recurrent VTE occurred in 252 patients (9 with OSA and 243 without OSA). The recurrence risk in the univariable and multivariable analysis was not increased in patients with OSA, regardless of the time of diagnosis (before or after index VTE or pooled). VTE phenotype was significantly more often PE with or without associated deep vein thrombosis in the first event and recurrence for OSA patients compared to non-OSA patients. The risk of death was not increased in the OSA population compared to non-OSA patients in multivariable analysis. Conclusions: In patients with OSA and VTE, the risk of all-cause mortality and VTE recurrence after anticoagulation discontinuation was not increased compared to non-OSA patients.