Polyethylene (PE) fibers exhibit superb mechanical and geometrical properties with respect to their use as dispersed reinforcement in cement-based materials. However, the fiber–matrix interaction in such composites is known to be poor due to the lack of active functional groups on the fibers’ polymeric backbones, leading to the limited affinity of PE fibers toward water-based, cementitious matrices. Therefore, to exploit the reinforcing effect of PE fibers in cementitious composites fully, fiber–matrix interactions need to be enhanced by functionalizing the fibers with hydrophilic polar groups. In the article at hand, the effects of dopamine (DA) and tannic acid (TA) surface functionalization and their combinations on interfacial properties with a high-strength, limestone-calcined clay cement (LC3) matrix have been explored. To assess the morphological changes as well as the physical–chemical properties of the fibers under investigation, they were characterized by environmental scanning electron microscopy (ESEM), Energy-dispersive X-ray spectroscopy (EDX), atomic force microscopy (AFM), X-ray photoelectron spectroscopy (XPS), thermogravimetric analysis (TGA), and zeta-potential (ZP). The presence of a DA and TA (DA/TA) coating layer was confirmed by ESEM and AFM images for modified samples, which showed rougher surfaces along with uniform coating distributions, proven via mapping images as well. TGA results yielded coating amounts of 7.8, 1.5, 1.5, 2.3 and 1.0 wt% for samples with DA/TA portions of 100/0, 70/30, 50/50 and 30/70 and 0/100, respectively. Compared with the pristine PE fiber, the DA/TA surface modification of PE fibers improved the tensile strength and modulus of elasticity values by 29% and 36%, respectively. According to micromechanical investigations, maximum pullout force and interfacial shear strength in specimens with modified fibers were three times higher than for the reference fibers, while fiber pullout energy was as much as six times higher.