Brettanomyces bruxellensis is one of the most damaging species for wine quality, and tools for controlling its growth are limited. In this study, thirty-nine strains belonging to Saccharomyces cerevisiae and B. bruxellensis have been isolated from wineries, identified and then tested against a panel of thirty-nine killer yeasts. Here, for the first time, the killer activity of Ustilago maydis is proven to be effective against B. bruxellensis. Mixed cultures in winemaking conditions show that U. maydis CYC 1410 has the ability to inhibit B. bruxellensis, while S. cerevisiae is fully resistant to its killer activity, indicating that it could be used in wine fermentation to avoid the development of B. bruxellensis without undesirable effects on the fermentative yeast. The characterization of the dsRNAs isolated and purified from U. maydis CYC 1410 indicated that this strain produces a KP6-related toxin. Killer toxin extracts were active against B. bruxellensis at pH values between 3.0 and 4.5 and temperatures comprised between 15 °C and 25 °C, confirming their biocontrol activity in winemaking and wine aging conditions. Furthermore, small amounts (100 AU/ml) of killer toxin extracts from U. maydis significantly reduced the amount of 4-ethylphenol produced by B. bruxellensis, indicating that in addition to the growth inhibition observed for high killer toxin concentrations (ranging from 400 to 2000 AU/ml), small amounts of the toxin are able to reduce the production of volatile phenols responsible for the aroma defects in wines caused by B. bruxellensis.