Tarhana is a traditional cereal product fermented by lactic acid bacteria (LAB) and yeast strains that has gained special interest recently as an infant nutrition. Tarhana contains wheat flour, yogurt, and various vegetables that might create a microbiological toxicological risk, especially forBacillus cereusandStaphylococcus aureus. In this study, characterization of the metabolites responsible for antibacterial activity ofPediococcus acidilacticiPFC69 andLactococcus lactisPFC77 strains obtained from tarhana was performed, and antibacterial effects were detected againstB. cereusATCC 11778 andS. aureusATCC 29213 during the fermentation. A total of 12,800 AU/mL antibacterial activity was observed for the supernatants of the PFC69 and PFC77 strains that were found to be stable at high temperature and in low pH conditions and sensitive to proteases, suggesting the antimicrobial metabolite is a bacteriocin. These bacteriocins were further purified and their molecular sizes were determined as 4.5 and 3.5 kDa, respectively. Importantly, inoculation of PFC69 and PFC77 to tarhana dough significantly decreasedB. cereusATCC 11778 andS. aureusATCC 29213 amounts from the fifth day of fermentation compared to the control dough samples.P. acidilacticiPFC69 andL. lactisPFC77 strains were concluded as bioprotective cultures for tarhana and these strains were offered for other cereal-based fermentations.