Coal combustion waste reaches huge amount that causes environmental problem. In modern world, wastes generated from an industry can be used by another industry as raw material. Bottom ash, a coal combustion waste, has found less usage area compared to fly ash in cement and concrete areas. Concrete paving block can be a good material to recycle bottom ash. Experimental works were fulfilled to investigate influences of recycling bottom ash in production of concrete paving blocks in this study. Three bottom ashes obtained from different coal burning plants were used. Elemental analysis, mineral characterization, and particle morphology of bottom ashes were determined by XRF, XRD, and SEM analyses, respectively. In production of blocks, cement was substituted with bottom ashes at 10%, 20%, and 30%. Unit weight, absorption, freeze-thaw, abrasion, and leaching tests were performed on specimens. Splitting tensile and compressive strength tests were also performed to determine the mechanical properties of the paving block. It can be concluded that bottom ashes can be used up to 20% replacement ratio in production of concrete paving blocks. It is also emphasized that freezing and thawing, and wear resistant concrete paving clocks can be obtained, even using bottom ash waste.