Objective: Peripheral arterial disease (PAD) often hinders the cardiac rehabilitation program. The aim of this study was evaluating the relative cost-effectiveness of new rehabilitation strategies which include the diagnosis and treatment of PAD in patients with coronary artery disease (CAD) undergoing cardiac rehabilitation. Data Sources: Best-available evidence was retrieved from literature and combined with primary data from 231 patients. Methods: We developed a Markov decision model to compare the following treatment strategies: 1. cardiac rehabilitation only; 2. ankle-brachial index (ABI) if cardiac rehabilitation fails followed by diagnostic work-up and revascularization for PAD if needed; 3. ABI prior to cardiac rehabilitation followed by diagnostic work-up and revascularization for PAD if needed. Quality-adjusted-life years (QALYs), life-time costs (US $), incremental cost-effectiveness ratios (ICER), and gain in net health benefits (NHB) in QALY equivalents were calculated. A threshold willingness-to-pay of$75 000 was used. Results: ABI if cardiac rehabilitation fails was the most favorable strategy with an ICER of $44 251 per QALY gained and an incremental NHB compared to cardiac rehabilitation only of 0.03 QALYs (95% CI: -0.17, 0.29) at a threshold willingness-topay of$75 000/ QALY. After sensitivity analysis, a combined cardiac and vascular rehabilitation program increased the success rate and would dominate the other two strategies with total lifetime costs of \$30 246 a quality-adjusted life expectancy of 3.84 years, and an incremental NHB of 0.06 QALYs (95%CI:-0.24, 0.46) compared to current practice. The results were robust for other different input parameters. Conclusion: ABI measurement if cardiac rehabilitation fails followed by a diagnostic work-up and revascularization for PAD if needed are potentially cost-effective compared to cardiac rehabilitation only.