Background: The type of sprayable surface impacts on residual efficacy of insecticide used in indoor residual spraying (IRS). However, there is limited data on common types of wall surfaces sprayed in Zanzibar and mainland Tanzania where IRS began in 2006 and 2007 respectively. The study investigated residual efficacy of micro-encapsulated lambda-cyhalothrin sprayed on common surfaces of human dwellings and domestic animal shelters in Zanzibar and mainland Tanzania. Methods: An experimental hut was constructed with different types of materials simulating common sprayable surfaces in Zanzibar and mainland Tanzania. Surfaces included cement plastered wall, mud-daub, white-wash, wood, palm-thatch, galvanized iron-sheets, burnt-bricks, limestone and oil-paint. The World Health Organization (WHO) procedure for IRS was used to spray lambda-cyhalothrin on surfaces at the dose of 20–25 mg/m2 . Residual efficacy of insecticide was monitored through cone bioassay using laboratory-reared mosquitoes; Kisumu strain (R–70) of Anopheles gambiae ss. Cone bioassay was done every fortnight for a period of 152 days. The WHO Pesticide Evaluation Scheme (WHOPES) threshold (80% mortality) was used as cut-off point for acceptable residual efficacy. Results: A total of 5,800 mosquitoes were subjected to contact cone bioassay to test residual efficacy of lambda-cyhalothrin. There was a statistically significant variation in residual efficacy between the different types of wall surfaces (r = 0.24; p < 0.001). Residual efficacy decreased with increasing pH of the substrate (r = −0.5; p < 0.001). Based on WHOPES standards, shorter residual efficacy (42-56 days) was found in wall substrates made of cement, limestone, mud-daub, oil paint and white wash. Burnt bricks retained the residual efficacy up to 134 days while galvanized iron sheets, palm thatch and wood retained the recommended residual efficacy beyond 152 days. Conclusion: The study revealed a wide variation in residual efficacy of micro encapsulated formulation of lambda-cyhalothrin across the different types of wall surfaces studied. In areas where malaria transmission is bimodal and wall surfaces with short residual efficacy comprise > 20% of sprayable structures, two rounds of IRS using lambda-cyhalothrin should be considered. Further studies are required to investigate the impact of sprayable surfaces on residual efficacy of other insecticides commonly used for IRS in Zanzibar and mainland Tanzania.