(1) Background: High-frequency heart rate variability (HF-HRV) is an essential ultradian rhythm that reflects the activity of the PNS to decelerate the heart. It is unknown how HF-HRV varies across the menstrual cycle (MC), and whether progesterone mediates this potential variation. (2) Methods: We enrolled 33 women in the study to attend eight clinic visits across the MC, during which we measured their resting HF-HRV and collected samples for the analysis of luteinizing hormone (LH) and progesterone. We realigned the study data according to the serum LH surge to the early follicular, mid-follicular, periovulatory, early luteal, mid-luteal and late luteal subphases. (3) Results: Pairwise comparisons between all the subphases showed significant differences between the early follicular and periovulatory subphases (beta = 0.9302; p </= 0.001) and between the periovulatory and early luteal subphases (beta = -0.6955; p </= 0.05). Progesterone was positively associated with HF-HRV in the early follicular subphase but not the periovulatory subphase (p </= 0.05). (4) Conclusions: The present study shows a significant drop in HF-HRV in the anticipation of ovulation. Further research in this area is critical given the marked cardiovascular disease mortality in women.