The climate of the Sahara and Arabian Deserts during the Little Ice Age is not well known, due to a lack of annually resolved natural and documentary archives. We present an annual reconstruction of temperature and aridity derived from Sr/Ca and oxygen isotopes in a coral of the desert-surrounded northern Red Sea. Our data indicate that the eastern Sahara and Arabian Deserts did not experience pronounced cooling during the late Little Ice Age (~1750–1850) but suggest an even more arid mean climate than in the following ~150 years. The mild temperatures are broadly in line with predominantly negative phases of the North Atlantic Oscillation during the Little Ice Age. The more arid climate is best explained by meridional advection of dry continental air from Eurasia. We find evidence for an abrupt termination of the more arid climate after 1850, coincident with a reorganization of the atmospheric circulation over Europe.