Nano-silica (NS) is deposited onto Carbon fibers (CFs) using electrophoretic deposition (EPD) to improve their bond to cementitious matrices. Two different voltage ranges and two deposition times were applied. The mobility of the negatively charged NS-colloids in deionized water in a controlled electric field was proven by zeta potential measurements and cyclic voltammetry (CV). Scanning electron microscopy and energy dispersive X-ray analysis (EDX) showed homogeneously distributed nano-silica particles on the surfaces of the CF. Thermo-gravimetric analysis (TGA) and single-fiber tensile tests were conducted to assess the impact of the parameters under investigation on the CF properties. Single-fiber pullout tests from a cement-based matrix showed markedly enhanced bond strength of the modified filaments, indicating improved reinforcing action of CF in cementitious composites. Storing the modified fibers in a cement pore solution showed that nano-silica deposits act as nucleating seeds for building calcium silicate hydrate (C–S–H) and calcite. This explains the enhanced bond properties.