In order to enhance the cryogenic mechanical properties of epoxy, graphene and multi-walled carbon nanotubes (MWCNTs) were used to modify epoxy synergistically. Room temperature (RT) and cryogenic (77 K) mechanical properties of graphene-MWCNTs/epoxy composites were systematically studied. The results show that simultaneous enhancements in cryogenic tensile strength, elastic modulus and impact strength can be achieved with 0.1wt% graphene and 0.5wt% MWCNTs. At this optimal formulation, the tensile strength of graphene-MWCNTs/epoxy composites reaches the highest value at both RT and 77 K, and is increased by 11.04% and 43.78% respectively, compared to pure epoxy. The cryogenic mechanical properties of epoxy can be synergistically enhanced by graphene and MWCNTs.