In this study, a series of cementitious composites with high toughness and flexural strength was obtained by melt-dispersing ultra-high molecular weight polyethylene (UHMWPE) into a cement matrix followed by water immersion. The structure and chemical composition of the composites were characterized by scanning electron microscopy (SEM) and energy dispersive spectroscopy (EDS). Three point bending tests showed that the flexural strengths of the composites were improved from 5.5 MPa to 18.2 MPa with the presence of 25 wt% UHMWPE, and could be further enhanced to 28.1 MPa with the addition of only 0.1 vol% oriented thermotropic liquid crystalline copolyester (TLCP) fibers. An adhesive test revealed that the interfacial binding force between polymer and fiber was much stronger than that between cement and fiber. Our findings provide a simple way for utilizing polymer to improve the interface between the fibers and cement matrix, consequently achieving a dramatic increase in the flexural strength and toughness.