Nabulsi cheese is the dominant white-brined cheese in Jordan and neighboring countries. Although this cheese is typically prepared using sheep’s milk, achieving large-scale production or attaining a specific quality involves the use of cows’ milk. Nabulsi cheese is kept in >18% brine for up to 1 year at room temperature (25 °C) and then soaked in water for desalting before eating. In this study, the effects of the milk type/combination used for production (100% sheep’s milk; 100% cows’ milk; 1:1, 3:1, or 1:3 sheep’s:cows’ milk mixture), desalting (salted vs. desalted cheese), and storage time (0, 6, and 12 months) on the cheese’s chemical composition directly after processing (in the salted form), texture (according to texture profile analysis “TPA”), and color (according to CIE lab color space) were assessed. The type or the combination of milk used does not affect the chemical composition of Nabulsi cheese, which was 43.35% ± 1.50 for moisture, 20.24% ± 0.59 for protein, 24.70% ± 1.53 for fat, 11.52% ± 0.60 for ash, 9.96% ± 0.44 for salt, and pH 6.43 ± 0.16. However, cheeses prepared using 100% sheep’s and 100% cows’ milk, respectively showed the highest (26.85%) and lowest (14.77%) yields. Desalting and milk type had the highest effects on cheese texture and color, respectively. Considering all tested parameters, mixing equal proportions of sheep’s and cows’ milk ensures that the Nabulsi cheese produced is similar to that produced from 100% sheep’s milk, albeit with increased cohesiveness (0.52 ± 0.07for cheese made from sheep’s milk and 0.59 ± 0.05 for 1:1 sheep’s: cows’ milk mixture).