An Optical Frequency Domain Reflectometry (OFDR) based fiber optic sensor scheme "embedded" in concrete for the purpose of structural health monitoring (SHM) of carbon concrete composites (C³) is presented. The design, while strengthening the concrete structure, also aims to monitor common SHM parameters such as strain and cracks. This was achieved by weaving the carbon fiber together with optical fiber, based on a specialized technique that uses an embroidery setup where both the carbon and optical fiber are woven on a water dissolvable polymer substrate. The performance of the sensing scheme was characterized in-situ utilizing the OFDR based technique and the results presented. The sensors embedded on a custom made concrete block were subjected to varying strain via a three point bending test to destruction and the results discussed. The intended dual-achievement of the scheme thus proposed in SHM and strengthening the C³ is demonstrated. The suitability of the OFDR scheme for C³ is combined with a fibre Bragg grating (FBG)-based approach, and discussed in detail.