This paper deals the changes in the internal structure of cement-tailings matrix composites (CTMC) with diverse dosages of polypropylene, polyacrylonitrile and glass fibers. To study the relations between the internal structure and strength properties, CTMC with and without fiber were subjected to various X-ray computed tomography (CT) and scanning electron microscopy before and after uniaxial compression. Results show that polypropylene fiber exhibited the strongest reinforcing effect, followed by polyacrylonitrile and glass fiber. Note that a 0.6% fiber dosage is considered as a critical point, and the strength of fiber reinforced CTMC increases first and then decreases. The grayscale value of non-reinforced N-1:6 is smaller than that of fiber-reinforced CTMC (except for B-0.6 sample), and the average grayscale value of each specimen after compression is reduced. When the fiber content is increased from 0 to 0.9%, the porosity of CTMC before compression is increased, and the damage value after compression is reduced and affected by the initial defect structure of CTMC. But, if the porosity before compression is less than 0.2%, the strength of fiber reinforced CTMC is less affected by the inherent structural integrity. In addition, there is a negative correlation between porosity and the grayscale value of fiber reinforced CTMC, and the failure mode is determined by the macroscopic cracks (size greater than 1000 mm(3)) penetrating the upper and lower end faces. This study shows that it is feasible to explore a correlation between the strength and meso-structure of CTMC using X-ray CT, which provides an excellent non-destructive tool.