Elephantorrhiza elephantina (Burch.) Skeels (Fabaceae) and Pentanisia prunelloides (Klotzsch ex Eckl. & Zeyh.) Walp. (Rubiaceae) are two medicinal plants used extensively in southern Africa to treat various ailments. Often, decoctions and infusions from these two plants are used in combination specifically for stomach ailments. The antimicrobial activities of the methanol and aqueous extracts of the rhizomes of the two plants, as well as the two active ingredients from the plants [(−)-epicatechin and palmitic acid] have been determined apart and in combination against Enterococcus faecalis (ATCC 29212), Escherichia coli (ATCC 8739) and Bacillus cereus (ATCC 11778). The minimum inhibitory concentration (MIC) values for the aqueous (0.50–16.00 mg/mL) and methanol (0.20–16.00 mg/mL) extracts independently demonstrated varied efficacies depending on the pathogen of study. When the two plants were combined in 1:1 ratios, synergistic to additive interactions (ΣFIC values 0.19–1.00) were noted. Efficacy for the two major compounds ranged between 0.13–0.63 mg/mL and mainly synergistic interactions were noted against E. faecalis and E. coli. The predominantly synergistic interactions noted between E. elephantina and P. prunelloides and major compounds, when tested in various ratios against these pathogens, provide some validation as to the traditional use of these two plants to treat bacterial gastrointestinal infections.