In this study, graphene nanosheets decorated with ZnO nanoparticles (NZG) were prepared from graphene oxide by a facile solvothermal method. Simultaneously, NZG as a substitute for conventional ZnO was incorporated into a rubber matrix. The NZG not only showed improved vulcanization efficiency but could also simultaneously play a reinforcing role for natural rubber (NR) nanocomposites. The results showed that the curing reaction of NR/NZG nanocomposites is significantly faster than that of neat NR. The dynamic and static mechanical properties and the gas barrier properties of NR/NZG nanocomposites were systematically investigated at different NZG contents. Compared with neat NR, the tensile strength, modulus at 300% strain and tear strength of the NR/NZG-2.5 nanocomposite are dramatically enhanced by 67.8%, 188.6% and 74.1%, respectively, at only 2.5 phr NZG content. The permeability of the NR/NZG-2.5 nanocomposite decreased by 53% compared to neat NR. The good dispersion of graphene and high vulcanization efficiency of ZnO nanoparticles, together with the enhanced interfacial interaction, is considered to be responsible for the significant synergetic effects in the improvement of the vulcanization characteristics, mechanical performance and gas barrier properties of the composites.