Controlling the widely distributed Listeria monocytogenes in soft cheeses has been a challenge for the cheese industry because of its ability to grow at low temperatures and resistance to salt and acidic conditions. Considerable interest has been shown in the application of lactic acid bacteria as biopreservatives for enhancing cheese quality and safety. The aim of this study was to select anti-Listeria LAB strains isolated from herbs, fruits and vegetables and to characterise their industrially relevant properties for potential roles as protective adjunct cultures in cheese manufacture. A total of 897 LAB isolates were screened for their anti-Listeria activity using an agar overlay assay. Fourteen LAB strains with strong activity were identified as Lactococcus lactis and all contained the nisin gene cluster. Four of these LAB isolates also exhibited detectable anti-Listeria activity in a milk medium. Despite showing high growth rates in milk, these wild Lc. lactis strains possessed slow lactose utilisation and acidification capacity. This suggested that the wild strains were likely undergoing mixed acid fermentation since ethanol was a major metabolic end product. When co-cultured in milk, the wild strains enhanced the post-growth lysis of an industrial Lc. lactis cheese starter strain but did not retard its milk acidification rate. The production of 3-methylbutanal, an important cheese odorant with a malty flavour, was found to increase 300-400 fold in milk and cheese fermented with wild and industrial strain combination. Whole genome sequencing of four wild strains revealed some genetic insights into their phenotypes. The wild strains lack the lactose utilisation operon (lacABCDFEG) commonly found in industrial strains, but contain genes encoding a putative β-galactosidase and a previously characterised alternative lactose assimilation pathway with slow lactose uptake. Wild strains also contain genes encoding α-keto-acid decarboxylase (kdcA) required for 3-methylbutanal production. These results suggest that wild Lc. lactis strains could be potentially used as biopreservative adjunct cultures to control growth of L. monocytogenes in soft cheeses and enhance cheese flavour development.