Cementitious-based strain sensors can be used as robust monitoring systems for civil engineering applications, such as road pavements and historic structures. To enable large-scale deployments, the fillers used in creating a conductive material must be inexpensive and easy to mix homogeneously. Carbon black (CB) particles constitute a promising filler due to their low cost and ease of dispersion. However, a relatively high quantity of these particles needs to be mixed with cement in order to reach the percolation threshold. Such level may influence the physical properties of the cementitious material itself, such as compressive and tensile strengths. In this paper, we investigate the possibility of utilizing a polymer to create conductive chains of CB more quickly than in a cementitious-only medium. This way, while the resulting material would have a higher conductivity, the percolation threshold would be reached with fewer CB particles. Building on the principle that the percolation threshold provides great sensing sensitivity, it would be possible to fabricate sensors using less conducting particles. We present results from a preliminary investigation comparing the utilization of a conductive paint fabricated from a poly-Styrene-co-Ethylene-co-Butylene-co-Styrene (SEBS) polymer matrix and CB, and CB-only as fillers to create cementitious sensors. Preliminary results show that the percolation threshold can be attained with significantly less CB using the SEBS+CB mix. Also, the study of the strain sensing properties indicates that the SEBS+CB sensor has a strain sensitivity comparable to the one of a CB-only cementitious sensor when comparing specimens fabricated at their respective percolation thresholds.