Matrix Gla Protein (MGP) is a strong vitamin K-dependent inhibitor of soft tissue calcification. We assessed the prevalence of functional vitamin K insufficiency, as derived from plasma desphospho-uncarboxylated MGP (dp-ucMGP), and investigated whether plasma dp-ucMGP is associated with all-cause and cardiovascular mortality in a large general population-based cohort. We included 4275 subjects (aged 53 ± 12 years, 46.0% male) participating in the prospective general population-based Prevention of Renal and Vascular End-Stage Disease (PREVEND) study. The prevalence of functional vitamin K insufficiency (i.e., dp-ucMGP > 500 pmol/L) was 31% in the total study population. This prevalence was significantly higher among elderly and subjects with comorbidities like hypertension, type 2 diabetes, chronic kidney disease, and cardiovascular disease (~50%). After 10 years of follow-up, 279 subjects had died, with 74 deaths attributable to cardiovascular causes. We found significant J-shaped associations of plasma dp-ucMGP with all-cause (linear term: hazard ratio (HR) (95% confidence interval (CI)) = 0.20 (0.12-0.33), p < 0.001; squared term: 1.14 (1.10-1.17), p < 0.001) and cardiovascular mortality (linear term: 0.12 (0.05-0.27), p < 0.001; squared term: 1.17 (1.11-1.23), p < 0.001). These associations remained significant after adjustment for potential confounders. Whether the correction of vitamin K insufficiency improves health outcomes needs to be addressed in future prospective intervention studies.