To guarantee structural safety, self-sensing concrete has garnered significant attention as an innovative solution for structural health monitoring. In particular, detecting cracks and their widths in concrete structures is an effective strategy for assessing damage conditions and extending service life. In this context, a novel cementitious composite is proposed, demonstrating an exceptional ability to monitor crack formation and width propagation through electrical signals generated by changes in relative electrical resistance (RER) of up to one hundred thousand percent—the highest value reported in the literature to date. Polyethylene (PE) fibers were initially functionalized with tannic acid (TA) and subsequently coated with TA-modified carbon nanotubes (CNTs) to make them electrically conductive for embedding into a normal-strength (NS) concrete matrix. The presence and approximate loading extent of CNTs on the fiber surface were examined using optical and scanning electron microscopes, X-ray photoelectron spectroscopy (XPS), and thermogravimetric analysis. The resulting CNT-coated fibers exhibited an average resistivity of 5.54 × 10⁻⁵ Ω cm ± 0.19 × 10⁻⁵ Ω cm, indicating excellent electrical conductivity and proper strain-sensing performance. The smart cementitious composites effectively detected crack formation and monitored crack width propagation, as evidenced by a sudden increase in RER (%) and its changes of up to 100,000 %, respectively. These electrical feedback signals were highly distinguishable from other influencing factors, such as weathering conditions, representing a major advancement compared to similar studies.