Medicine sellers are widely used for fever and malaria treatment in sub-Saharan Africa, but concerns surround the appropriateness of drugs and information provided. Because there is increasing interest in improving their services, we reviewed the literature on their characteristics and interventions to improve their malaria-related practices. Sixteen interventions were identified, involving a mixture of training/capacity building, demand generation, quality assurance, and creating an enabling environment. Although evidence is insufficient to prove which approaches are superior, tentative conclusions were possible. Interventions increased rates of appropriate treatment, and medicine sellers were willing to participate. Features of successful interventions included a comprehensive situation analysis of the legal and market environment; buy-in from medicine sellers, community members and government; use of a combination of approaches; and maintenance of training and supervision. Interventions must be adapted to include artemisinin-based combination therapies, and their sustainability and potential to operate at a national level should be further explored.