Elucidating the evolutionary process of animal adaptation to deserts is key to understanding adaptive responses to climate change. Here we generated 82 individual whole genomes of four fox species (genus Vulpes) inhabiting the Sahara Desert at different evolutionary times. We show that adaptation of new colonizing species to a hot arid environment has probably been facilitated by introgression and trans-species polymorphisms shared with older desert resident species, including a putatively adaptive 25 Mb genomic region. Scans for signatures of selection implicated genes affecting temperature perception, non-renal water loss and heat production in the recent adaptation of North African red foxes (Vulpes vulpes), after divergence from Eurasian populations approximately 78 thousand years ago. In the extreme desert specialists, Rueppell’s fox (V. rueppellii) and fennec (V. zerda), we identified repeated signatures of selection in genes affecting renal water homeostasis supported by gene expression and physiological differences. Our study provides insights into the mechanisms and genetic underpinnings of a natural experiment of repeated adaptation to extreme conditions.