Cheese has been listed as one of four priority food groups intended for salt reduction reformulation. The present study aimed to investigate the possibility of producing Serbian white brined cheese (Homoljski Sir) with half of NaCl, three quarters of NaCl and all NaCl replaced with KCl (Na50, Na25 and Na0, respectively). Basic composition, proteolysis and texture profile parameters were monitored during 60 days of ripening. At the end of ripening, an acceptance test was conducted by untrained consumers (N = 46). According to the cluster analysis based on hedonic scores, three clusters emerged: male consumers (47.8%), agreeable consumers (30.4%) and highly educated female consumers (21.8%). Both partial and a total salt replacement had no effect on the course of proteolytical changes, the texture and basic composition during ripening. Female consumers did not accept any level of salt substitution, while male consumers showed dislike only for the Na0 cheese. Almost 80% of all consumers liked moderately-to-very-much the Na25 cheese variant. It implies that it is worth considering the production of cheese with 50–75% of NaCl replaced with KCl. The addition of natural flavoring and clear labeling of the sodium reduction should accompany the salt replacement strategy.