Cement-tailings matrix composites (CTMC) have problems such as high brittleness and poor crack resistance when subjected to high stresses corresponding to large depths. To overcome these problems, the feasibility of adding fiber to CTMC were explored by using numerous uniaxial compressive strength, longitudinal wave velocity, splitting tensile, three-point bending resistance tests and scanning electron microscopy analysis. To produce the cemented backfills, three different fibers such as polypropylene fiber, polyacrylonitrile fiber, and glass fiber were used to improve their mechanical strength properties. The quality and performance of fiber reinforced CTMC structures were compared with non-reinforced ones (without fiber addition). Results show that: (1) the addition of fiber increases the uniaxial compressive and splitting tensile strength, and the load-bearing capacity after the peak of the load-span deflection curve of filling, but the bending strength enhancement effect is not ideal. (2) When the fiber content increases from 0.3% to 0.9%, the uniaxial compressive strength, splitting tensile and flexural strength of fiber-reinforced backfills usually followed a trend of increasing first and then decreasing. Among the fibers, the comprehensive reinforcement effect of polypropylene fiber is the best. (3) Uniaxial compressive strength and longitudinal wave velocity of CTMC followed a function increasing trendy = 0.216 + 0.031e(1.743x) (4) The interfacial behavior between the fiber and the matrix is an important factor in suppressing the crack. The addition of fiber causes the failure form of CTMC to transform into the ductile failure.