Dairy products are very susceptible to fungal spoilage, which causes economic losses and is a public health concern due to the possible production of mycotoxins. Several novel approaches have been proposed to delay the growth of mold in cheese. Among these, adding a protective culture is particularly interesting in view of increasing consumer demand for naturally preserved foods. The aim of this study was to select a new protective culture and validate its effectiveness as an inhibitor of fungal proliferation in cottage-type cheese. Food-grade bacteria (88 strains) were screened for inhibition of four spoilage molds commonly isolated from cheese. Strains of Propionibacterium and Lactobacillus were the most active. Seven strains were selected and tested further, alone and in pairs, for their abilities to prevent Penicillium chrysogenum growth in a solidified dairy matrix and in cottage cheese. Lactobacillus rhamnosus A238 alone or in combination with Bifidobacterium animalis subsp. lactis A026 inhibited mold growth for at least 21 days at 6 °C, due probably to the production of secondary metabolites and/or competition for nutrients. Overall, our findings show that these strains inhibit molds, some of them acting in synergy, and have potential for use as bio-preservatives in fresh cheese.