A total of 330 lactic acid bacteria isolated from South African red wines during alcoholic and malolactic fermentations and 9 commercial malolactic bacteria starter cultures were screened for antimicrobial activity. Of the entire screened isolates, 26 strains, belonging to the species Lactobacillus plantarum, Lactobacillus paracasei, Lactobacillus hilgardii and Oenococcus oeni, showed activity towards various wine-related and non-wine-related indicator strains. A PCR-based screening revealed the presence of the plantaricin encoding genes plnA, plnEF, plnJ and plnK in five selected Lb. plantarum strains. Furthermore, a co-culture experiment with Lb. plantarum and Enterococcus faecalis was performed. A complete inhibition of cell growth of Ent. faecalis was observed within 72 h. Four putative bacteriocin-encoding genes in the genome of O. oeni were identified and sequenced.