Background: The effect of heat stress on livestock production is a worldwide issue. Animal performance is influenced by exposure to harsh environmental conditions potentially causing genotype-by-environment interactions (G × E), especially in highproducing animals. In this context, the main objectives of this study were to (1) detect the time periods in which heifer fertility traits are more sensitive to the exposure to high environmental temperature and/or humidity, (2) investigate G × E due to heat stress in heifer fertility traits, and, (3) identify genomic regions associated with heifer fertility and heat tolerance in Holstein cattle. Results: Phenotypic records for three heifer fertility traits (i.e., age at first calving, interval from first to last service, and conception rate at the first service) were collected, from 2005 to 2018, for 56,998 Holstein heifers raised in 15 herds in the Beijing area (China). By integrating environmental data, including hourly air temperature and relative humidity, the critical periods in which the heifers are more sensitive to heat stress were located in more than 30 days before the first service for age at first calving and interval from first to last service, or 10 days before and less than 60 days after the first service for conception rate. Using reaction norm models, significant G × E was detected for all three traits regarding both environmental gradients, proportion of days exceeding heat threshold, and minimum temperature-humidity index. Through single-step genome-wide association studies, PLAG1, AMHR2, SP1, KRT8, KRT18, MLH1, and EOMES were suggested as candidate genes for heifer fertility. The genes HCRTR1, AGRP, PC, and GUCY1B1 are strong candidates for association with heat tolerance. Conclusions: The critical periods in which the reproductive performance of heifers is more sensitive to heat stress are trait-dependent. Thus, detailed analysis should be conducted to determine this particular period for other fertility traits. The considerable magnitude of G × E and sire re-ranking indicates the necessity to consider G × E in dairy cattle breeding schemes. This will enable selection of more heat-tolerant animals with high reproductive efficiency under harsh climatic conditions. Lastly, the candidate genes identified to be linked with response to heat stress provide a better understanding of the underlying biological mechanisms of heat tolerance in dairy cattle.