It is understood that the frost protection afforded by entrained air voids in cement-based materials is dependent on their size and distribution or spacing factor. The common practice of adding air-entraining admixtures (AEAs) to concretes and mortars demands economical quality control measures of the air-entrained voids. However, conventional methods for qualifying air content in fresh cement-based materials, such as the pressure, volume, and gravimetric methods, measure only total air volume and cannot assess size (i.e., allow discrimination between entrained and entrapped air voids) or spacing. Ultrasonic monitoring may present an alternative in situ approach for these measurements. In this investigation, using matched pairs of transducers, ultrasonic pulses were transmitted through fresh cement paste specimens (containing 0.0 % up to 0.6 % AEA by weight of cement). The received signals were recorded every 5 min during the first 6 h and then every 15 min thereafter. Analysis of the signals shows strong distinctions between specimens with and those without the AEA. In general, the addition of AEA suppresses the peak-to-peak signal strength, pulse velocity, and peak frequency of the signal transmissions through the specimens. The data also suggest correlations between Vicat setting times, heat of hydration, and autogenous strain and ultrasonic metrics. The findings of this research should be most appropriate as a foundation for an inversion process and improved air-entrainment detection methods.