The Lubombo Spatial Development Initiative is a joint development program between the governments of Mozambique, Swaziland, and South Africa, which includes malaria control as a core component of the initiative. Vector control through indoor residual spraying (IRS) was incrementally introduced in southern Mozambique between November 2000 and February 2004. Surveillance to monitor its impact was conducted by annual cross-sectional surveys to assess the prevalence of Plasmodium falciparum infection, entomologic monitoring, and malaria case notification in neighboring South Africa and Swaziland. In southern Mozambique, there was a significant reduction in P. falciparum prevalence after the implementation of IRS, with an overall relative risk of 0.74 for each intervention year (P < 0.001), ranging from 0.66 after the first year to 0.93 after the fifth intervention year. Substantial reductions in notified malaria cases were reported in South Africa and Swaziland over the same period. The success of the program in reducing malaria transmission throughout the target area provides a strong argument for investment in regional malaria control.