Extreme temperatures at critical crop stages reduce grain yield. Combinations of sowing date and cultivar that favour earlier flowering reduce the likelihood of heat stress but increase the risk of frost at critical stages. Current models are unable to predict pulse yield in response to frost and heat, hence our focus on phenology. Our aim was to model phenological variation with sowing date and cultivar for lentil and faba bean against the climatic patterns of frost and heat in 45 Australian locations that spanned 29°S - 41°S, 11-340 m.a.s.l., and 1-423 km to the coast. For both crops, modelled mean and standard deviation of time to flowering were close to actuals and mean prediction error was below 5%. Comparison of actual and modelled time to flowering returned r = 0.89 (n = 121, P < 0.0001) and modelling efficiency = 0.73 for lentil, and r = 0.96 (n = 123, P < 0.0001) and modelling efficiency = 0.84 for faba bean. Curves fitted to the time-course of frost (< 0 °C) and heat (> 34 °C) probabilities between 1957 and 2018 were used to estimate the date of 10% frost probability and the date of 30% heat probability as the boundaries of a frost-heat risk window. Out of the 45 locations, 12 were frost-free but with risk of heat, 7 were heat-free but with risk of frost, 3 were frost- and heat-free, and 23 featured a window defined by both frost and heat boundaries. Frost variables discriminated locations more strongly than heat variables. Geographical patterns in thermal regimes emerged that were associated with latitude, altitude and continentality. Realised warming between 1957 and 2018 shortened the time to modelled critical stage in most locations, particularly in early-sown crops. Comparisons of the probability curves of frost and heat between 1957-1985 and 1986-2018 showed, with few exceptions, an asymmetry between delayed late frost (up to 44 d) and earlier heat onset (up to 11 d), with a narrowing of the frost-heat risk window from 46-90 d for the period 1957-1985 to 34-64 d for 1986-2018. We identified a dominant role of frost as (i) the main discriminating factor among geographically distinct locations, (ii) the main source of variation of the frost-heat window, and (iii) a putatively increased risk factor with climate change. Adaptation to frost is critical for pulses despite warming trends. Increased frost tolerance can directly improve yield and indirectly contribute to reduce risk of heat and drought later in the season.