Intake of vegetables is recommended for the prevention of myocardial infarction (MI). However, vegetables make up a heterogeneous group, and subgroups of vegetables may be differentially associated with MI. The aim of this study was to examine replacement of potatoes with other vegetables or subgroups of other vegetables and the risk of MI. Substitutions between subgroups of other vegetables and risk of MI were also investigated. We followed 29,142 women and 26,029 men aged 50-64 years in the Danish Diet, Cancer and Health cohort. Diet was assessed at baseline by using a detailed validated FFQ. Hazards ratios (HR) with 95% CI for the incidence of MI were calculated using Cox proportional hazards regression. During 13.6 years of follow-up, 656 female and 1,694 male cases were identified. Among women, the adjusted HR for MI was 1.02 (95% CI: 0.93, 1.13) per 500 g/week replacement of potatoes with other vegetables. For vegetable subgroups, the HR was 0.93 (95% CI: 0.77, 1.13) for replacement of potatoes with fruiting vegetables and 0.91 (95% CI: 0.77, 1.07) for replacement of potatoes with other root vegetables. A higher intake of cabbage replacing other vegetable subgroups was associated with a statistically non-significant higher risk of MI. A similar pattern of associations was found when intake was expressed in kcal/week. Among men, the pattern of associations was overall found to be similar to that for women. This study supports food-based dietary guidelines recommending to consume a variety of vegetables from all subgroups.