Since many rural-poor Lozi people of Sesheke District (Western Province, Zambia) that suffer from sexually transmitted infections do not usually access public health facilities; they turn to traditional healers who administer remedies extracted from medicinal plants. However, the medicinal plants used for sexually transmitted infections and data on the usage of plants in Sesheke District in particular and Western Province in general have not been documented. In this study, an ethnobotanical survey was conducted to document the indigenous knowledge of medicinal plants that alleviate symptoms of sexually transmitted infections in Sesheke District, Western Province, Zambia. Using semi-structured interviews and questionnaires, ethnobotanical data were collected from twenty traditional healers that manage patients presenting with sexually transmitted infections. The results showed that 52 plant species in 25 families and 43 genera were used to treat gonorrhoea, syphilis, chancroid, chlamydia, genital herpes, and ano-genital warts. Sexually transmitted infections were frequently managed using the following plants: Terminalia sericea, Strychnos cocculoides, Ximenia caffra, Cassia abbreviata, Cassia occidentalis, Combretum hereroense, Combretum imberbe, Dichrostachys cinerea, Boscia albitrunca, Momordica balsamina and Peltophorum africanum. Many of these plants have putative antimicrobial activities which may justify their roles as natural remedies for sexually transmitted infections. Further studies are needed to determine the dosages, minimum inhibitory concentrations, biological activities and toxicities, and characterise the plants’ chemical compounds.