Structural health monitoring to assess the safety, durability and performance of structures can be performed by non-destructive methods such as the measurement of impedance in self-sensing cement-based elements. Cement-based materials, like mortars and concretes, generally have high electrical resistivity but the addition of carbon-based fillers and fibres decreases their electrical resistivity and thus enhances their self-sensing capabilities. In this study, two waste carbon-based fillers, namely, used foundry sand and gasification char were compared to commercial graphene nanoplatelets and used to produce self-sensing cement mortars, both with and without recycled or virgin carbon fibres. The mortars were tested in terms of their mechanical and electrical properties as well as their propensity to capillary water absorption. The results demonstrate that gasification char alone is the best carbonaceous waste for decreasing the electrical resistivity (−42%) and water absorption (−17%) of mortars, while their compressive strength remains unaltered. Moreover, although there is a slight reduction in compressive strength and an increase in water suction when gasification char is coupled with fibres, the combination of fillers and fibres has a synergistic effect in decreasing mortars’ electrical resistivity, especially when recycled carbon fibres are used (−80%).