Staphylococcus aureus is a gram positive opportunistic pathogen and a major concern for both animal and human health worldwide. In some contexts where Lactic Acid Bacteria (LAB) are the normal dominant microbiota, such as in fermented food or in the vaginal ecosystem, S. aureus sometimes colonises, persists, expresses virulence factors and produces food poisoning or urogenital infections, respectively. Studies on the interactions between LAB and S. aureus began a few decades ago and were pursued to shed light on the inhibitory capabilities that LAB might have on S. aureus growth and/or enterotoxin production in fermented foodstuffs. These early studies had the aim of developing methods to prevent staphylococcal food poisoning, thus improving food safety. More recently, the concept of vaginal probiotic LAB has emerged as a promising way to prevent urogenital infections, S. aureus being one of the potential pathogens targeted. This review provides an up-to-date look at the current hypotheses of the mechanisms involved in the inhibition of S. aureus by LAB in both the vaginal ecosystem and in fermented food ecosystems. We also emphasise that post-genomic approaches can now be envisioned in order to study these diverse and complex interactions at the molecular level. Further works in this field will open up new avenues for methods of biocontrol by LAB and/or for biotechnological uses of LAB-compounds to fight against the long-standing, yet incumbent menace of staphylococcal infection.