The effect of natamycin as a fungal control agent in natural black olive fermentation according to the traditional anaerobic system was studied. Black Conservolea olives were subjected to spontaneous fermentation in 8% (w/v) NaCl brine solution (control treatment) or brine supplemented with 0.01% (w/v) natamycin (active compound) for an overall period of 60 days. The changes in the microbial association (lactic acid bacteria, yeasts, Enterobacteriaceae), pH, titratable acidity, organic acids, and volatile compounds were monitored throughout fermentation. The initial microbiota consisted of lactic acid bacteria, yeasts, and Enterobacteriaceae. The addition of natamycin in the brine inhibited the growth of yeasts, without affecting the population dynamics of bacteria, resulting in a more vigorous fermentation with higher titratable acidity compared to spontaneous control process. Moreover, the presence of natamycin inhibited mould spoilage caused by the development of fungal mycelium on the surface of the brine during the traditional anaerobic fermentation system employed widely in Greece in natural black olive processing. Natamycin could be an important component of a processing system to control fungal growth in natural black olive fermentation and at the same time it has the potential to enhance the process by favouring the growth of the indigenous population of lactic acid bacteria against other competing microorganisms.