Background: While observational data suggest a higher risk of coronary artery disease with frequent egg consumption, only limited and inconsistent data are available on the relation of egg consumption with stroke. Objective: The primary objective was to assess whether egg consumption is associated with a higher risk of ischemic and hemorrhagic stroke among US veterans. Methods: In a prospective cohort study of US veterans from the Million Veteran Program (MVP), egg intake was collected through a self-reported food frequency questionnaire at baseline. Incidence of stroke was ascertained via ICD9/ICD10 codes from the electronic health records. Multivariable Cox proportional hazard models were used to estimate the multivariable adjusted hazard ratios. Results: A total of 233,792 veterans (91.6% men) were studied with a mean age of 65.6 ± 11.7 years. During a mean follow-up of 3.3 years, a total of 5740 cases of fatal and non-fatal ischemic stroke and 423 cases of fatal and non-fatal hemorrhagic stroke occurred. Median egg consumption was 2–4 eggs/week. Crude incidence rates for acute ischemic stroke were 6.5, 7.2, 7.1, 7.4, 8.0, 8.1, and 8.6 cases per 1000 person-years for egg consumption of <1/month, 1–3/month, 1/week, 2–4/week, 5–6/week, 1/day, and ≥2/day, respectively. Corresponding multivariable adjusted hazard ratios (95% CI) were 1.00 (ref), 1.10 (0.96–1.25), 1.09 (0.96–1.23), 1.10 (0.98–1.25), 1.16 (1.01–1.33), 1.20 (1.03–1.40), and 1.22 (1.03–1.45) controlling for age, sex, ethnicity, body mass index, diabetes, smoking, alcohol intake, modified DASH score, and education (p linear trend 0.0085). For hemorrhagic stroke, multivariable adjusted hazard ratios (95% CI) after controlling for age, sex, ethnicity, body mass index, modified DASH score, and level of education were 1.00 (ref), 1.28 (0.96–1.72), 1.22 (0.93–1.61), and 1.19 (0.88–1.61) for egg consumption of <1/week, 1/week, 2–4/week, 5+/week, respectively. Conclusion: Our data are consistent with a positive association of egg consumption with acute ischemic stroke but not hemorrhagic stroke among veterans.