The urgent need to reduce the environmental impact of building materials has led to the recent development of low-clinker binders, such as limestone calcined clay cement (LC³). The possibility of using LC³ to produce cement-based composites with high mechanical properties and reduced environmental impact is certainly of great interest. In this study, two LC³ mixtures with different mechanical performances (low and high strength) were investigated. Chopped carbon fibers coming from end-of-life prepreg carbon textiles (rCF), recovered through pyrolysis, and virgin carbon fibers (vCF) were used to reinforce the matrices. Different fiber dosages were investigated, up to 1.5% by volume. Fiber reinforced LC³ composites were characterized through compression and bending tests. The addition of both rCF and vCF results in a decrease in matrix workability, by increasing fiber volume. On the other hand, rCF were able to increase both the compression and bending performances of the cementitious composites, up to 66% and 53%, respectively. Remarkably, no significant differences were found in using rCF instead of vCF.