Cemented paste backfill (CPB) is used extensively in underground mining operations worldwide. However, CPB technology is not widely used in China’s western eco-environment frangible area because of the sources, costs, and mechanical properties of the material. This study aims to investigate and better understand the mechanical properties of aeolian sand-based cemented backfilling with different properties (water/cement ratio, aeolian sand content, fly ash content, and Portland cement content) at early-age curing times (1, 3, 7, 28 days). Based on microstructural analyses (e.g. X-ray diffraction and SEM studies) of tested CPB materials, an experiment was designed to study the early-age strength of nine different CPB materials. The obtained results reveal that water/cement ratio, aeolian sand content, fly ash content and Portland cement content can affect the properties of CPB materials. The experimental results can help to better assess and predict the mechanical properties of aeolian sand-based cemented backfilling materials. The findings of this study have significant implications for CPB practices in China’s western eco-environment frangible area.