Background: Medicare uses the Centers for Medicare & Medicaid Services Hierarchical Condition Category (CMS-HCC) model to predict patients' annualized Medicare costs in value-based payment programs. The CMS-HCC model does not include measures of frailty, and prior research shows that it systematically underpredicts costs for frail Medicare beneficiaries. Objective: To determine whether a claims-based frailty index can improve Medicare cost prediction. Design: Retrospective cohort study. Setting: Medicare Current Beneficiary Survey linked to Medicare claims, 2006 to 2013. Participants: 16 535 community-dwelling, fee-for-service beneficiaries representing 26 705 patient-years. Measurements: Patient frailty status was classified using a validated claims-based frailty index. The association between the frailty index and annualized Medicare costs was examined, and regression methods were used to compare observed Medicare costs versus predictions based on the standard CMS-HCC model with and without the frailty index. Results: Mean costs were $5724 for the 8910 patients classified as robust (46.4% of patient-years), $12 462 for the 8405 prefrail patients (41.6%), $26 239 for the 2215 mildly frail patients (9.6%), and $44 586 for the 593 patients classified as moderately to severely frail (2.5%). The frailty index addition to the CMS-HCC model predicted on average an additional $2712, $7915, and $16 449 in costs for prefrail, mildly frail, and moderately to severely frail patients, respectively, beyond the CMS-HCC model alone. On average, the model with the frailty index addition resulted in more accurate predictions of costs for patients at all 4 levels of frailty. However, observed costs remained more widely distributed than predictions from the enhanced model at all levels of frailty. Limitation: The claims-based index is a proxy for frailty and is likely less accurate than an in-person examination. Conclusion: The CMS-HCC model with the frailty index addition is an improvement over current Medicare cost prediction.