It is anticipated that the use of fly ash in concrete will be significantly limited in the future due to recent restrictions on coal burning power plants to reduce air pollution. This paper aims to study the compatibility between some natural supplementary cementitious materials (SCMs): including perlite (PL), pumice (PM), and zeolite (ZL) with one type of superplasticizer and two types of air-entraining admixtures (AEA), mainly by analyzing the rheological properties and air-void system, respectively. It was found that both the porosity and amount of organic content of SCMs can play a significant role in air stability in cementitious materials. The organic AEA was found to be more effective than the synthetic AEA to produce a stable air system in cementitious materials due to the low required admixture dosage, while the synthetic air entraining admixture showed superior performance in the retention of the air system and resulted in better compatibility compared to the organic air-entraining admixture. In general, the addition of SCMs in non-air-entrained concrete mixtures resulted in similar rheological properties as well as similar compressive strength compared to the air-entrained concrete. This confirms that the air void system has successfully been introduced in the concrete mixture without any incompatibilities.