The extensive generation of solid waste, such as coal gangue, imposes considerable environmental strain. Converting such waste into cemented coal gangue paste backfill materials (CCGPB) presents an effective solution. This study aims to determine the uniaxial compressive strength (UCS) and liquidity of CCGPB using experimental methods and machine learning-based numerical analysis while addressing the challenges of slow curing and low early strength associated with traditional CCGPB. This study investigates the hardening characteristics of red mud-modified CCGPB (RCCGPB) through UCS and slump tests. The internal micro-pore structure and hydration process of RCCGPB were analyzed using scanning electron microscopy (SEM), mercury intrusion porosimetry (MIP), Fourier transform infrared spectroscopy (FTIR), and thermogravimetric analysis (TG). Furthermore, a random forest (RF) model was utilized to assess the impact of three variables on the evolution of UCS. The results indicated that the highest UCS was achieved with a fly ash content of 12% and a red mud content of 8%. Microscopic analysis revealed that the primary hydration products include cementitious silicate hydrate, aluminum hydroxide carbonate, and ettringite. The RF model analysis indicated that curing age had the most substantial influence on UCS development. This research provides a theoretical foundation and data reference for the design and application of RCCGPB.