For the first time in science of metal-matrix composite materials, "Gum-metalgraphene" nanocomposite is synthesized which has a Gum metal (Ti-Nb-Ta-Zr-O alloy) matrix containing graphene nanoinclusions. To do so, we created a novel method to synthesize Gum metal and "Gum-metal-graphene" nanocomposite. In the latter case, micromechanical splitting of thermo-exfoliated graphite is used as graphene source. With Xray analysis, we demonstrated that the phase compositions of Gum metal specimens and the nanocomposite matrix are identical to one of typical Gum metal compositions reported in literature.