This paper deals the relationship between compressive strength and internal crack formation (e.g., crack width and volume) of cement-fiber-tailings matrix composites (CFTMC) using an industrial computed tomography system and scanning electron microscopy. Two types of fibers (polypropylene PP and polyacrylonitrile PAN) were used to manufacture CFTMC with a constant cement-to-tailings ratio, solid content and curing time of 1:6, 75 wt% and 14 days, respectively. The results showed that strength gaining of CFTMC increased remarkably with fiber additions which effectively improve its toughness. When compared to samples without fibers, the compressive strength of CFTMC was the highest because of the reduced interconnection between pores and high particle packing density. The internal structure analysis showed that the maximum crack widths of CFTMC increased when the fiber content increased from 0.3 to 0.6 wt%, regardless of fiber type, growing the crack volumes of samples. The failure pattern of all CFTMC samples was mainly tensile, shear and mixed failure (tensile/shear), and a high strength value accompanies with a big volume of crack. At last, the findings of this study may offer a key reference for fiber-reinforced backfills, which can lift their strength, stability and integrity behavior under extreme conditions, such as rock burst, squeezing ground, blast or seismic event.