The transmission of malaria across the Arabian Peninsula is governed by the diversity of dominant vectors and extreme aridity. It is likely that where malaria transmission was historically possible it was intense and led to a high disease burden. Here, we review the speed of elimination, approaches taken, define the shrinking map of risk since 1960 and discuss the threats posed to a malaria-free Arabian Peninsula using the archive material, case data and published works. From as early as the 1940s, attempts were made to eliminate malaria on the peninsula but were met with varying degrees of success through to the 1970s; however, these did result in a shrinking of the margins of malaria transmission across the peninsula. Epidemics in the 1990s galvanised national malaria control programmes to reinvigorate control efforts. Before the launch of the recent global ambition for malaria eradication, countries on the Arabian Peninsula launched a collaborative malaria-free initiative in 2005. This initiative led a further shrinking of the malaria risk map and today locally acquired clinical cases of malaria are reported only in Saudi Arabia and Yemen, with the latter contributing to over 98% of the clinical burden.