Significant headway has been made in the global fight against malaria in the past decade and as more countries enter the elimination phase, attention is now focused on identifying effective strategies to shrink the malaria map. Saudi Arabia experienced an outbreak of malaria in 1998, but is now on the brink of malaria elimination, with just 82 autochthonous cases reported in 2012. A review of published and grey literature was performed to identify the control strategies that have contributed to this achievement. The number of autochthonous malaria cases in Saudi Arabia decreased by 99.8% between 1998 and 2012. The initial steep decline in malaria cases coincided with a rapid scaling up of vector control measures. Incidence continued to be reported at low levels (between 0.01 and 0.1 per 1,000 of the population) until the adoption of artesunate plus sulfadoxine-pyrimethamine as first line treatment and the establishment of a regional partnership for a malaria-free Arabian Peninsula, both of which occurred in 2007. Since 2007, incidence has decreased by nearly an order of magnitude. Malaria incidence is now very low, but a high proportion of imported cases, continued potential for autochthonous transmission, and an increased proportion of cases attributable to Plasmodium vivax all present challenges to Saudi Arabia as they work toward elimination by 2015.