This study was conducted to explore the optimum proportion of zeolite and zeolite-kaolin as additives to cement clinker and gypsum samples, while maintaining the strength properties of produced environmentally sustainable cements. According to the British standard method, zeolite was added to cement clinker in proportions of 5-12% and 10-12% by weight, respectively, in the preparation of samples of zeolite-containing cement and zeolite-kaolin-based cement. Kaolin was used as a second additive as 10-20% of the total weight. The compressive strength tests were performed on base cement samples according to a standard procedure given in ASTM C109 Compressive Strength of Hydraulic Cement. These values were compared with those of the reference sample and the Omani allowable limits. The results indicated that the best compressive strength values were obtained with 88% cement clinker, 5% gypsum, and 7% zeolite for the zeolite-containing cement. Quantities of 70% cement clinker, 5% gypsum, 10% zeolite, and 15% kaolin gave the best results for zeolite-kaolin-based cement, resulting in a substitution of than 25% cement clinker. The study concluded that the partial cement clinker replacement using zeolite/kaolin combination may have a great influence on the reduction of CO2 emission and energy saving in cement manufacturing.