Two-dimensional (2D) materials, which commonly have much higher optical nonlinearity and faster carrier dynamics than their bulk counterparts, hold huge potential for use in nonlinear optical devices, especially in ultrafast mode-locked fiber lasers. Graphene has ultrafast carrier dynamics but the optical absorption is low and the modulation depth is small. It is nontrivial to combine graphene with other 2D materials so as to form a heterostructure with improved optical properties. In particular, recent research has shown that the 2D transition metal carbide (TMC) Mo2C has a very large nonlinear absorption coefficient and can be used as a saturable absorber for mode-locking pulse generation. However, the nonlinear optical properties of the graphene-Mo2C heterostructure have not been investigated. In this work, by directly growing Mo2C nanosheets on the monolayer graphene film and forming the heterostructure, a new kind of saturable absorber was prepared with considerate nonlinear absorption coefficient and large modulation depth. Such a new saturable absorber was evanescently interacted with the side-polished fiber and successfully delivered femtosecond pulse generation at 1550 nm. The combination of two semi-metal 2D materials has enabled the ease of mode locking and stable soliton state pulse generation.