Graphene oxide (GO)/hydrogenated carboxylated nitrile–butadiene rubber (HXNBR) composites were prepared by a solution-blending method. The GO monolayers with 0.9 nm in thickness, more than 2.5 μm in width and 3 μm in length were exfoliated from natural flake graphite by a modified Hummers method and could be further dispersed homogeneously in HXNBR matrix even for the GO contents up to 1.3 vol.%. The addition of 0.44 vol.% of GO nanosheets enhanced the tensile strength and modulus at 200% elongation of HXNBR by more than 50% and 100%. This is believed to be due to strong interfacial interactions between the oxygen-containing functional groups on the surfaces of GO nanosheets and the carboxyl groups in HXNBR. Moreover, this general observation is further supported by the increase of the glass transition temperature of HXNBR from −23.2 to −21.6 °C, at a GO content of 1.3 vol.%. The results indicated that GO efficiently reinforced HXNBR due to the good dispersion and strong interfacial interactions.