When our human ancestors migrated out of Africa, they faced a considerably harsher climate, but the extent to which human cranial morphology has adapted to climate is still debated. In particular, it remains unclear when such facial adaptations arose in human populations. Here, we explore climate-associated features of face shape in a worldwide modern human sample using 3D geometric morphometrics and a novel application of reduced rank regression. Based on these data, we assess climate adaptations in two crucial Upper Palaeolithic human fossils, Sungir and Mladeč, both of which have been archaeologically associated with a boreal-to-temperate climate. We found several aspects of face shape, especially the relative dimensions of the external and internal nose as well as of the maxillary sinuses, that are strongly associated with temperature and humidity, even after accounting for auto-correlation due to geographical proximity of populations. For these features, both fossils revealed adaptations to a dry environment, with Sungir being strongly associated with cold and Mladeč with warm-to-hot temperatures. As both fossils are dated among the earliest recent modern humans in Europe, our results suggest a relatively fast rate of climate adaptation in human respiratory morphology.