H2 production via water electrolysis plays an important role in hydrogen economy. Hence, novel cheap electrocatalysts for the hydrogen evolution reaction (HER) are constantly needed. Here, we describe a simple method for the preparation of composite catalysts for H2 evolution, consisting in simultaneous reduction of the graphene oxide film, and electrochemical deposition of Ni on its surface. The obtained composites (Ni@rGO), compared to pure electrodeposited Ni, show an improved electrocatalytic activity towards HER in alkaline media. We found that the activity of the Ni@rGO catalysts depends on the surface composition (Ni vs. C mole ratio) and on the level of structural disorder of the rGO support. We suggest that HER activity is improved via Hads spillover from the Ni particles to the rGO support, where quick recombination to molecular hydrogen is favored. A deeper insight into such a mechanism of H2 production was achieved by kinetic Monte-Carlo simulations. These simulations enabled the reproduction of experimentally observed trends under the assumption that the support can act as a Hads acceptor. We expect that the proposed procedure for the production of novel HER catalysts could be generalized and lead to the development of a new generation of HER catalysts by tailoring the catalyst/support interface.