The authors recently investigated the use of conductive concrete to enhance nondestructive evaluation (NDE) capa- bilities. Preliminary results have shown that a conductive concrete can facilitate the utilization of an eddy current technique, where damages in a conductive specimen were easier to detect compared with a non-conductive substrate. While such results demonstrated the promise of using conductive concrete to facilitate and potentially accelerate the NDE process, the fabrication of an homogeneous conductive concrete is technically or economically challenging, depending on the conductive filler used in the process. In this paper, we propose a new cementitious composite to accelerate NDE. The composite uses inexpensive carbon black particles (CB) and a block-copolymer. The purpose of the block co-polymer, a styrene-ethylene-butylene-styrene (SEBS), is to facilitate the creation of conductive chains, therefore reducing the necessary concentration of conductive filler required to achieve electrical percolation. Several cementitious composite specimens of various concentrations of CB are fabricated, and results show that the utilization of SEBS reduces the electrical percolation threshold by approximately 50% with a gain on electrical conductivity relative to a non-conductive specimen mix of approximately 33%. Strain-sensing tests also demonstrate that SEBS-based specimens have good sensing properties, but lag behind those of conductive concrete specimens fabricated with CB only.