Background The interplay between mental and physical health remains poorly understood. We investigated whether psychological distress is associated with risk of myocardial infarction (MI) and stroke in a population-based prospective study. Methods and Results We included participants without prior stroke/MI from the New South Wales 45 and Up Study. We categorized baseline psychological distress as low, medium, and high/very high on the 10-item Kessler Psychological Distress scale and identified stroke and MI through linkage to hospital admission and mortality records. We obtained sex and age-stratified adjusted and unadjusted hazard ratios for the association between psychological distress and MI and stroke. We investigated for interaction between psychological distress and each of age and sex. Among 221 677 participants, 16.2% and 7.3% had moderate and high/very high psychological distress at recruitment, respectively. During 4.7 (±0.98 SD) years of follow-up, 4573 MIs and 2421 strokes occurred. Absolute risk of MI and stroke increased with increasing psychological distress level. In men aged 45 to 79 years, high/very high versus low psychological distress was associated with a 30% increased risk of MI (fully adjusted hazard ratios, 1.30; 95% CI, 1.12–1.51), with weaker estimates in those aged ≥80 years. Among women, high/very high psychological distress was associated with an 18% increased risk of MI (adjusted hazard ratio, 1.18; 95% CI, 0.99–1.42) with similar findings across age groups. In the age group of participants aged 45 to 79 years, high/very high psychological distress and male sex had a supra-additive effect on MI risk. Similar estimates were observed for stroke, with high/very high psychological distress associated with a 24% and 44% increased stroke risk in men and women, respectively, with no evidence of interaction with age or sex. Conclusions Psychological distress has a strong, dose-dependent, positive association with MI and stroke in men and women, despite adjustment for a wide range of confounders.