The effect of substitution of NaCl with Potassium chloride (KCl) in brine solution on proteolysis of halloumi cheese was investigated. Halloumi cheeses were made and kept in 4 different brine solutions (18% w/w), including only NaCl (HA; control); 3NaCl:1KCl (w/w) (HB); 1NaCl:1KCl (w/w) (HC); 1NaCl:3KCl (w/w) (HD); and stored for 56 d at 4 °C. Proteolysis was assessed using water-soluble nitrogen (WSN), trichloroacetic acid-soluble nitrogen (TCA-SN), phosphotungstic-soluble nitrogen (PTA-SN), urea polyacrylamide gel electrophoresis (urea-PAGE), and peptide patterns. WSN and TCA-SN contents were similar in all experimental cheeses. Peptide patterns of the pH 4.6 N fraction and urea-PAGE showed no significant difference between halloumi cheeses kept in various NaCl/KCl mixtures (HB, HC, HD) and control (HA). Sodium and potassium contents showed positive correlations with WSN and PTA-SN. There was an inverse correlation between calcium (Ca) contents and WSN and PTA-SN. Correlations between Ca and Na or K were negative at the same salt treatment.