People tend to rely on air temperatures when in reality the lethality of heat is probably more linked to the wet-bulb temperature.
The human body has a natural resting temperature of about 37°C, and metabolism of course generates more heat constantly, so we constantly have to shed that heat. When the temperature is low, we can rely purely on conducting the heat into the atmosphere to shed the heat (which is probably why internal body temperature is higher than the atmosphere!). At higher temperatures, conduction is less efficient, or sometimes even adds heat load into the system (at above 37°C, obviously), so we start relying on evaporative cooling (i.e., sweat) to cool us down.
The wet-bulb temperature is the minimum temperature that can be reached by evaporative cooling. So when the wet-bulb temperature is in the mid-30s °C… people start to become literally unable to regulate their core body temperature, and the heat is lethal. Wet-bulb is largely a combination of the temperature and humidity, but unfortunately, it's not typically reported in most weather reports, so people go off of the air temperature (and the humidity) that is reported.
Which is a long-winded way of saying "the humidity matters a lot for how much a given temperature is bearable." I don't know what environment you come from purely by rural New South Wales, but my first guess is the semi-arid and thus low-humidity bush regions of the state, which means the apparent wet-bulb temperature of 37-40°C would be a lot lower than the equivalent 37-40°C for most of the humid continental climates of Europe.