Graphene with fascinating properties has been deemed as an excellent reinforcement for cementitious composites, enabling construction materials to be smarter, stronger, and more durable. However, some challenges such as dispersion issues and high costs, hinder the direct incorporation of graphene-based reinforcement fillers into cementitious composites for industrial production. The combination of graphene with conventional fibers to reinforce cement hence appears as a more promising pathway especially towards the commercialization of graphene for cementitious materials. In this review paper, a critical and synthetical overview on recent research findings of the implementation of graphene in fiber-reinforced cementitious composites was conducted. The preparation and characterization methods of hybrid graphene-fiber fillers are first introduced. Mechanical reinforcing mechanisms are subsequently summarized, highlighting the main contribution of nucleation effect, filling effect, interfacial bonding effect, and toughening effect. The review further presents in detail the enhancements of multifunctional properties of graphene-fiber reinforced cementitious composites, involving the interfacial properties, mechanical properties, durability, electrical conductivity, and electromagnetic interference shielding. The main challenges and future prospects are finally discussed to provide constructive ideas and guidance to assist with relevant studies in future.