The coarse aggregate backfill has high rigidity, poor toughness, and local energy storage accumulation, which is easy to cause safety problems. The addition of fiber can improve the toughness and ductility of the backfill and enhance its mechanical properties. Using coarse aggregate, waste rock, rod sand and river sand from Longshou Mine of Jinchuan as raw materials, the effect of fiber blending process on uniaxial compressive strength of backfill was studied. Design-Expert software was used to analyze the influences of various factors (slurry mass concentration, fiber volume rate, and cement content) on the early mechanical properties of backfill and optimize the parameters. The nonlinear regression models between the early uniaxial compressive strength value and various factors were established to reveal the interaction effects between different factors, and the cost of filling slurry material after adding fiber was calculated. The results show that the addition of fiber can significantly improve the compressive strength of the backfill. Compared with the blank group without fiber (3.03 MPa), the strength of the backfill in scheme Ⅱ (wet mixing of filling materials firstly, and then adding fibers in three stages) is 4.35 MPa, with an increase of 43.56%, which is the optimal scheme. The significant influencing factors of early mechanical properties of fiber reinforced backfill are ordered as slurry mass concentration > cement content > fiber volume rate. The interaction effect between slurry mass concentration and cement content is the most significant, which verifies the reliability of the regression model. After adding fibers, the cost of filling slurry material only increases by 0.67%−15.6%. On the premise of meeting the strength requirements of the backfill, the content of coarse aggregate and cement can be appropriately reduced, which can also reduce the cost.