Background: Though Maytenus senegalensis is one of the medicinal plants widely used in traditional medicine to treat infectious and inflammatory diseases in Africa, there is a lack of safety data regarding its use. Therefore, the study aimed to asselss the safety and tolerability of the antimalarial herbal remedy M. senegalensis. Material and Methods: The study design was an open-label, single-arm, dose-escalation. Twelve eligible male healthy Tanzanians aged 18 to 45 years were enrolled in four study dose groups. Volunteers’ safety and tolerability post-investigational-product administration were monitored on days 0 to 7,14, and 56. Results: There were no deaths or serious adverse events in any of the study groups, nor any adverse events that resulted in premature discontinuation. The significant mean changes observed in WBC (p = 0.003), Neutrophils (p = 0.02), Lymphocytes (p = 0.001), Eosinophils (p = 0.009), Alanine aminotransferase (p = 0.002), Creatinine (p = 0.03) and Total bilirubin (p = 0.004) laboratory parameters were not associated with any signs of toxicity or clinical symptoms. Conclusions: M. senegalensis was demonstrated to be safe and tolerable when administered at a dose of 800 mg every eight hours a day for four days. This study design may be adapted to evaluate other herbal remedies.