Research question: What are the differences in menstrual blood lymphocytes between controls, patients with recurrent pregnancy loss (RPL) and patients with unexplained infertility (uINF)? Design: Prospective study including 46 healthy controls, 28 RPL and 11 uINF patients. A feasibility study compared lymphocyte compositions of endometrial biopsies and menstrual blood collected during the first 48 h of menstruation in seven controls. In all patients, peripheral and menstrual blood from the first and subsequent 24 h were analysed separately by flow cytometry, focusing on the main lymphocyte populations and natural killer (NK) cell subsets. Results: The first 24 h of menstrual blood resembles the uterine immune milieu as tested by endometrial biopsy. RPL patients showed significantly higher menstrual blood CD56⁺ NK cell numbers than controls (mean ± SD: 31.13 ± 7.52% versus 36.73 ± 5.4%, P = 0.002). Menstrual blood CD56^dimCD16^bright NK cells within the CD56⁺ NK cell population were decreased in RPL (16.34 ± 14.65%, P = 0.011) and uINF (15.7 ± 5.91%, P = 0.02) patients versus control (20.42 ± 11.53%). uINF patients had the lowest menstrual blood CD3⁺ T cell counts (38.81 ± 5.04%, control versus uINF: P = 0.01) and cytotoxicity receptors NKp46 and NKG2D on CD56^brightCD16^dim cells were higher in uINF (68.12 ± 11.84%, P = 0.006; 45.99 ± 13.83%, P = 0.01, respectively) and RPL (NKp46: 66.21 ± 15.36%, P = 0.009) patients versus controls. RPL and uINF patients had higher peripheral CD56⁺ NK cell counts versus controls (11.42 ± 4.05%, P = 0.021; 12.86 ± 4.29%, P = 0.009 versus 8.4 ± 3.5%). Conclusions: Compared with controls, RPL and uINF patients had a different menstrual blood-NK-subtype profile, indicating an altered cytotoxicity. In future studies, this non-invasive analysis might enable identification and monitoring of patients receiving immunomodulatory medications.