Hispanic style soft non-fermented cheeses, such as queso fresco (QF) have been linked to outbreaks and recalls. Salmonella is one of the main causes of these incidents. Due to lack of ripening or post-processing antimicrobial treatments, incorporating GRAS antimicrobials to production process may be a suitable approach to minimize microbial risk in QF. The aim of this study was to evaluate the efficiency of nisin (N), caprylic acid (CA) and trans-cinnamaldehyde (CN) as single or combined treatments to reduce Salmonella populations in QF during storage. Batches of QF were inoculated after curding with approx. 4 Log CFU/g of 5-strain cocktails of Salmonella and stored at 8 °C for 20 days. The final Salmonella counts in control samples ranged from 6.96 to 7.14 Log CFU/g. Application of CN at 0.6 g/kg inhibited Salmonella growth during storage, resulting in at least 3 Log CFU/g difference with the untreated controls (p < 0.05). Addition of N (0.5 g/kg) and CA (0.4 g/kg) with CN (0.3 and 0.6 g/kg) further enhanced the antimicrobial activity resulting in complete suppression of growth and even caused a 1 Log CFU/g reduction by the end of the experimental period compared to initial counts. Samples treated with the combined treatment (N, CA, CN) were evaluated in a consumer panel (n = 112). Participants preferred the control and commercial QF to the treated samples. However, treated samples with 0.3 g/kg CN were still within the acceptable range of neutral to like slightly. Results obtained, revealed that combined treatment of N, CA and CN can provide a solution to reduce the count of Salmonella in QF, whether in process or during storage.