Purpose: Heat intolerance (HI) is determined in the Israel Defense Force according to a heat tolerance test (HTT) before returning to duty after an exertional heat stroke (EHS) event. Recently, increased numbers of female combatants resulted in an increased number of EHS cases among women and a higher percentage of heat intolerance (HI) individuals. We aimed to evaluate the differences between tolerance to heat among women performing an HTT in relation to their menstrual cycle phase. Method: Thirty-three female participants were sorted into two groups: HI and heat tolerant (HT) according to two HTTs performed during both the luteal and follicular phases of the menstrual cycle or while consuming and during a break from consuming contraceptives. Results: HT women had an 18% higher maximal oxygen uptake (p < 0.005, 95% CI [2.6,9.8]) and 1.2% lower skin temperature in the HTT at the during and follicular phases (p < 0.01, 95% CI [0.12,0.77]) and 1.7% lower at the off and luteal phases (p < 0.001, 95% CI [0.34,0.92]). The mean sweat rate was 14% lower among the HI group only at the HTT at the during and follicular phases (p < 0.05, 95% CI (3,88)]). Conclusion: We found that HT can be predicted using aerobic capacity and core body temperature. Moreover, during the luteal phase, women presented altered thermoregulation that decreased the probability of being HT. This emphasizes the importance of considering the HT/HI criteria in the HTT for women, according to their aerobic ability and menstrual-cycle phase.