This study aims to recycle the coal bottom ash (CBA) for making environmentally friendly construction bricks. In the brick proportion, CBA was employed as fine aggregate to replace 0, 30, 50, 70, 85, and 100% of stone powder. The results demonstrate that, the compressive strength, ultrasonic pulse velocity, electrical resistance, and thermal conductivity of the 28-day bricks were in the ranges of 16.1 ÷ 61.3 MPa, 3469 ÷ 4208 m/s, 20.2 ÷ 54.6 kΩ.cm, and 0.75 ÷ 2.2 W/mK, respectively. According to scanning electron microscopy analysis, the rise in CBA content was associated with an increase in the number of voids and pores of bricks, which led to a less dense microstructure and a negative impact on the brick’s quality. However, all specimens created for this investigation met the standards of the official Vietnamese standard and were categorized as grade M15.0 or higher according to their qualities.