Background Over the past decade malaria intervention coverage has been scaled up across Africa. However, it remains unclear what overall reduction in transmission is achievable using currently available tools. Methods and Findings We developed an individual-based simulation model for Plasmodium falciparum transmission in an African context incorporating the three major vector species (Anopheles gambiae s.s., An. arabiensis, and An. funestus) with parameters obtained by fitting to parasite prevalence data from 34 transmission settings across Africa. We incorporated the effect of the switch to artemisinin-combination therapy (ACT) and increasing coverage of long-lasting insecticide treated nets (LLINs) from the year 2000 onwards. We then explored the impact on transmission of continued roll-out of LLINs, additional rounds of indoor residual spraying (IRS), mass screening and treatment (MSAT), and a future RTS,S/AS01 vaccine in six representative settings with varying transmission intensity (as summarized by the annual entomological inoculation rate, EIR: 1 setting with low, 3 with moderate, and 2 with high EIRs), vector–species combinations, and patterns of seasonality. In all settings we considered a realistic target of 80% coverage of interventions. In the low-transmission setting (EIR∼3 ibppy [infectious bites per person per year]), LLINs have the potential to reduce malaria transmission to low levels (<1% parasite prevalence in all age-groups) provided usage levels are high and sustained. In two of the moderate-transmission settings (EIR∼43 and 81 ibppy), additional rounds of IRS with DDT coupled with MSAT could drive parasite prevalence below a 1% threshold. However, in the third (EIR = 46) with An. arabiensis prevailing, these interventions are insufficient to reach this threshold. In both high-transmission settings (EIR∼586 and 675 ibppy), either unrealistically high coverage levels (>90%) or novel tools and/or substantial social improvements will be required, although considerable reductions in prevalence can be achieved with existing tools and realistic coverage levels. Conclusions Interventions using current tools can result in major reductions in P. falciparum malaria transmission and the associated disease burden in Africa. Reduction to the 1% parasite prevalence threshold is possible in low- to moderate-transmission settings when vectors are primarily endophilic (indoor-resting), provided a comprehensive and sustained intervention program is achieved through roll-out of interventions. In high-transmission settings and those in which vectors are mainly exophilic (outdoor-resting), additional new tools that target exophagic (outdoor-biting), exophilic, and partly zoophagic mosquitoes will be required. Please see later in the article for the Editors' Summary