Purpose: No previous study has evaluated the relationship between vitamin K and frailty. Thus, we assessed the relationship between vitamin K status and frailty over 13 years in the Longitudinal Aging Study Amsterdam (LASA). Methods: Prospective cohort study with 644 community-dwelling adults ≥ 55 years from the LASA cohort. In 2002–2003, plasma desphospho-uncarboxylated matrix Gla protein (dp-ucMGP) was measured as marker of vitamin K status through a sandwich ELISA. Frailty was measured at baseline and in four follow-up examinations with the LASA Frailty Index (LASA-FI), which was used as both a continuous and a dichotomous measure (FI ≥ 0.25), as indicator of the degree of frailty and frailty risk, respectively. Statistical analyses were performed with multivariable generalized estimating equations using the lowest dp-ucMGP tertile, reflecting a high vitamin K status, as reference. Results: The mean (SD) age was 59.9 (2.9) years, and 54% were female. Compared with the lowest tertile, the medium and highest dp-ucMGP tertile were associated with a higher degree of frailty [1.40, 95% confidence interval (0.01–2.81) and 1.62, (0.18–3.06), respectively. P trend: 0.03]. Additionally, the medium and highest dp-ucMGP tertile had a higher odds ratio of frailty [1.75 (1.11–2.77) and 1.63 (1.04–2.57), respectively]. The degree of frailty increased over time, but the differences by dp-ucMGP tertiles existed since baseline and remained stable during follow-up. Conclusions: Baseline plasma low vitamin K status was associated with a greater degree of frailty and frailty risk in this cohort of older adults, which highlights the importance of ensuring an optimal nutritional status of this vitamin to prevent frailty in later life.