The article presents the results of tests on the frost resistance, water absorption, and compressive strength of concretes made with three types of cement: CEM I, CEM II/B-M (S-V), and CEM III/A, evaluated after different curing periods (28, 56, and 90 days). Additionally, to assess the effects of the minimum 4% air entrainment recommended by the EN 206 standard, concrete mixes with the same composition but containing an air-entraining admixture in a constant amount of 0.15% by cement mass, were prepared. For a more comprehensive characterization of the concretes, tests were also conducted on the concrete mixes and the physical properties of the concretes, such as density, water absorption, and total porosity, were determined. The paper also presents significant results on the pore distribution in the air-entrained concretes, confirming the achievement of very good basic air-entrainment parameters in all concretes. Based on the test results, it was found that both the type of cement and the introduction of an air-entraining admixture significantly influence not only the frost resistance of the concretes but also their compressive strength depending on the curing time of the samples. This is particularly evident in the low-clinker cements CEM II and CEM III. It was observed that in the case of concretes with these cements, it is possible to achieve an almost zero decrease in compressive strength after 150 cycles of freezing and thawing after 90 days of curing.