High-performance polyethylene (PE) fibers possess unique features to develop advanced cementitious composites with superior mechanical properties. Nonetheless, due to their hydrophobic nature, such fibers can develop only a poor interfacial affinity between themselves and the water-based cementitious matrices, which restricts a full exploitation of their intrinsic properties. The work described here is an expeditious and environmentally friendly strategy to enhance the bond strength in PE fiber-reinforced cementitious composites through utilization of polydopamine (PDA) surface modification. Environmental scanning electron microscopy (ESEM), X-ray photoelectron spectroscopy (XPS), thermogravimetric analysis (TGA), water contact angle, and electrokinetic measurements were applied to characterize the surface properties of the fibers under investigation. Moreover, fiber-matrix interactions were assessed by single-fiber pullout from a cementitious matrix with respect to dopamine concentration and modification time. Compared to the unmodified reference sample, a noticeable increase in maximum pullout load, interfacial shear strength, and fiber pullout energy was achieved with the modified fibers. This was explained by the formation of active hydrophilic groups on the fiber surfaces, which groups enhance the fibers’ wettability and yield better interaction with the cementitious matrix. Furthermore, the modified fibers exhibit increased tensile strength, modulus of elasticity, and suitable stability in a highly alkaline environment as well.