The ecologic impact of concrete-based building materials requires re-thinking in the construction industry towards sustainable and bio-based materials. This paper describes fiber-reinforced cementitious composites prepared from limestone-calcined clay cement (LC³) matrix and polyethylene fibers. Molecularly thin films of the bio-inspired adhesion promoter polydopamine (PDA) were applied to improve the adhesive interaction between fibers and cement matrix and produce strain-hardening cementitious composites (SHCC). Thorough characterization by AFM, electrokinetic measurements and X-ray photoelectron spectroscopy (XPS) showed that a dense PDA layer with sufficient reactive functional groups was present already after 1 h PDA deposition time. Excess PDA was removed from the fibers during storage in alkaline solutions but the film was not degraded completely. Single-fiber pullout tests revealed an enhanced fiber–matrix adhesion already by using cleaned fibers but the effect was stronger with PDA-modified fibers. Finally, the fiber preparation was upscaled to study the effect of the PDA fiber modification on the mechanical stability of SHCC on the mesoscale, an approach that is quite rare in the literature. Uniaxial tension tests showed that a big influence of the matrix on the tensile strength, however, the fibers' bridging strength is improved by the use of PDA-coated fibers compared to pristine and cleaned fibers.