Background. The World Health Organization has recommended pilot implementation of a candidate vaccine against malaria (RTS,S/AS01) in selected sub-Saharan African countries. This exploratory study aimed to estimate the costs of implementing RTS,S in Burkina Faso, Ghana, Kenya, Mozambique, and Tanzania. Methods. Key informants of the expanded program on immunization at all levels in each country were interviewed on the resources required for implementing RTS,S for routine vaccination. Unit prices were derived from the same sources or from international price lists. Incremental costs in 2015 US dollars were aggregated per fully vaccinated child (FVC). It was assumed the four vaccine doses were either all delivered at health facilities or the fourth dose was delivered in an outreach setting. Results. The costs per FVC ranged from US$25 (Burkina Faso) to US$37 (Kenya) assuming a vaccine price of US$5 per dose. Across countries, recurrent costs represented the largest share dominated by vaccines (including wastage) and supply costs. Non-recurrent costs varied substantially across countries, mainly because of differences in needs for hiring personnel, in wages, in cold-room space, and equipment. Recent vaccine introductions in the countries may have had an impact on resource availability for a new vaccine implementation. Delivering the fourth dose in outreach settings raised the costs, mostly fuel, per FVC by less than US$1 regardless of the country. Conclusions. This study provides relevant information for donors and decision makers about the cost of implementing RTS,S. Variations within and across countries are important and the unknown future price per dose and wastage rate for this candidate vaccine adds substantially to the uncertainty about the actual costs of implementation.