The high energy demand and CO₂ emissions associated with Portland cement (PC) production have intensified the need for more sustainable cementitious materials. In this context, low-clinker and blended cements have gained increasing attention. Limestone Calcined Clay Cement (LC3) offers significant potential to mitigate environmental impacts, particularly using low-grade and waste-derived clays. Although numerous studies have explored the enhancement of engineering properties in cementitious systems using synthetic fibers, the fiber–matrix interactions in LC3 systems—especially those incorporating clays derived from construction and demolition waste (CDW)—remain underexplored. This study investigates the processing and mechanical behavior of fiber-reinforced LC3 composites incorporating hollow brick (HB) and ceramic waste tiles (CWT) clays. By incorporating polyvinyl alcohol (PVA) fibers, the cracking resistance of fiber-reinforced LC3 composites (FRLC3)—formulated with only 22.5% Portland cement by binder mass—was enhanced, leading to improved tensile properties, despite slight reductions in compressive strength and flowability. The findings demonstrate that CDW-based low-grade clays are viable alternatives for producing low-clinker containing FRLC3 composites with superior tensile performance, offering a sustainable substitute for fly ash, which is increasingly scarce in many regions.