Ordinary cemented paste backfill (CPB) is characterised by high brittleness, low tensile strength, and degraded bearing capacity under severe stress conditions. Reinforcing CPB with fibres can effectively improve such characteristics. The behaviour of polypropylene (PP) fibre as a reinforcement for mine tailing-based CPB is well understood but for coal ash-based CPB, is never explored. Therefore, this study examined the effect of PP fibre on the mechanical and microstructural properties of coal ash-based CPB. The CPB was prepared at 75 wt% solid concentration with 0.0, 0.3,–0.5 wt% fibre content of dry solid weight. The results show that the uniaxial compressive strength of CPB specimens was increased between 69.81 and 199.47 kPa (7 days), 95.13–216.96 kPa (14 days), and 164.88–298.1 kPa (28 days), respectively, for varying fibre content between 0 and 0.5%. It revealed that the fibre reinforcement had a maximum influence on the strength development rate of 7 days (185.73%) cured CPB specimens than 14 days (128.07%) and 28 days (80.8%). The fibre addition increased the peak strain of specimens and transformed their failure mode from the appearance of longitudinal cracks in non-reinforced specimens to the several micro-cracks in reinforced specimens. The reinforcement further increased the 28 days elastic modulus from 249.05 to 339.68 kPa and tensile strength from 26.23 to 39.69 kPa. The SEM micrograph illustrated that the fibre-bridging effect is more pronounced with reinforcement in terms of reduced pore spaces, high compactness, and better fibre-matrix bonding.