COVID-19 vaccination temporarily lengthens the menstrual cycle. However, without knowing why this happens, we are limited in our ability to fully address ongoing concerns around menstrual health and COVID-19 vaccination. We assessed whether menstrual cycle timing (follicular or luteal phase) of COVID-19 vaccine administration is driving vaccine-associated cycle length changes. We used prospectively collected (2021-2022) menstrual cycle tracking data from 19,497 reproductive-aged users of the application ‘Natural Cycles’. We identified whether vaccine was delivered in the follicular or luteal phase and also included an unvaccinated control group. Our primary outcome was the adjusted within-individual change in cycle length (in days) from the average of the three menstrual cycles prior to the first vaccination cycle (unvaccinated controls were assigned a notional vaccine date). We also assessed if a clinically significant change in cycle length occurred (8 days or more). Individuals were mostly under age 35 (80.1%), and from North America (28.6%), continental Europe (33.5%) or the UK (31.7%). In the vaccinated group, the majority received an mRNA vaccine (63.8%). Individuals vaccinated in the follicular phase experienced an average 1-day longer adjusted cycle length with both a first or second dose of COVID-19 vaccine compared to their pre-vaccination average [1st dose: 1.00 day (98.75% CI 0.88, 1.13), 2nd dose 1.11 days (98.75% CI 0.93, 1.29)] whereas those vaccinated in the luteal phase and the unvaccinated control group experienced no change in cycle length [respectively, 1st dose -0.09 (-0.26, 0.07), 2nd dose 0.06 (-0.16, 0.29), unvaccinated notional 1st dose 0.08 (-0.10, 0.27), 2nd dose 0.17 (-0.04, 0.38). Those vaccinated during the follicular phase were also more likely to experience a clinically significant change in cycle length (>8 days; 1st dose: 6.8%) than those vaccinated in the luteal phase or unvaccinated (3.3% and 5.0%, respectively; p < 0.001). COVID-19 vaccine-related cycle length increases are associated with receipt of vaccination in the first half of the menstrual cycle (follicular phase) which is consistent with other known immune-related events (e.g. fever) that also cause temporary cycle length changes.