A study was undertaken on the durability of high-strength concrete (HSC) produced using locally available materials in the State of Missouri. Thirty-six (36) different mixtures were produced as HSC. 30% fly ash replacement by cement weight was utilized in the HSC mixtures, and ground granulated blast-furnace slag (GGBFS) was also substituted by 5% of the cement weight for some mixtures. The mixtures included locally available limestone as coarse aggregate. The mixtures without cement replacement displayed higher strength development at the end of 56 days. All the air-entrained mixtures performed well under 300 freezing and thawing cycles warranting a minimal level of air entrainment requirement. However, the samples in which GGBFS was utilized performed poorly relative to the other samples. Similar poor performance was obtained from the same samples in chloride permeability tests.