The objective of this investigation was comparing the penetration of chloride ions in ordinary and air-entrained concretes containing a waste material Fluidized Bed Combustion Fly Ash (FBCFA). All concretes were tested with 15% and 30% cement replacement by FBCFA, with the same water-binder ratio of 0.45. Two kinds of fly ash coming from fluid bed combustion in two power plants in Poland have been used. In this study the rapid chloride permeability test – Nordtest Method BUILD 492 method – was used. The microstructure of the concrete was analyzed on thin polished sections and the measurement of air voids sizes and their distribution, using digital image analysis, was carried on according to PN-EN 480-11:2008. Obtained results have shown a significant influence of partial cement replacement by FBCFA on the chloride ions movements in concrete. It has been found that this kind of addition reduced considerably the chloride ion penetration. The influence of air entrainment on the chloride diffusion coefficients was also measured and it was shown that application of air-entraining admixture for concretes with FBCFA reduce the chloride diffusion coefficient but it should be used with caution.