In Kenya, most people especially in rural areas use traditional medicine and medicinal plants to treat many diseases including malaria. Malaria is of national concern in Kenya, in view of development of resistant strains of Plasmodium falciparum to drugs especially chloroquine, which had been effective and affordable. There is need for alternative and affordable therapy. Many antimalarial drugs have been derived from medicinal plants and this is evident from the reported antiplasmodial activity. The aim of the study was to document medicinal plants traditionally used to treat malaria by the Digo community of Kwale district. Traditional health practitioners were interviewed with standardized questionnaires in order to obtain information on medicinal plants traditionally used for management of malaria. Twenty-five species in 21 genera and 16 families were encountered during the study. Celestraceae, Leguminosae and Rubiaceae families represented the species most commonly cited. Three plant species, namely; Maytenus putterlickioides, Warburgia stuhlmannii and Pentas bussei are documented for the first time for the treatment of malaria.