Coal bottom ash (CBA), a silica rich by-product of coal burning, has been primarily researched as a substitute construction material. This study investigates the effect of the treatment type and optimum dosage of CBA as a binder replacement in cement paste. Pulverisation, soaking and burning of CBA were conducted prior to mixing in order to enhance its innate physical and chemical characteristics. Materials from two Malaysian power plants, Kapar (K) and Tanjung Bin (TB), were used to examine the 'source effect' on the pozzolanic constituents of CBA. Subsequently, the compressive strength of the produced cement paste was investigated. The total pozzolanic content (SiO2, Al2O3, and Fe2O3) in CBA from K amounts to 63%, whereas it is merely 50% for TB. The compressive strengths of cement paste involving CBA at different levels of binder replacement were compared to gauge the effect of the treatment type. The cement paste made with untreated (raw) TB and K-CBA have both shown comparable and continuous declining trends in the compressive strength up to 50% cement replacement. At a liquid-to-binder (l/b) ratio of 0.35, the raw CBA samples showed relatively similar compressive strengths. For both sources, however, the compressive strengths of the pulverised CBA cement paste samples surpassed those utilising untreated CBA - signifying the positive impact of pulverising on the cementitious properties of CBA. The compressive strengths for the pulverised K-CBA and TB-CBA at 50% cement replacement were 24.3 and 27.3 MPa, respectively. These strengths are adequate for basic structural application, e.g. concrete pavers. Burning and soaking CBA have also improved the compressive strength, but to a lower extent.