Graphene nanosheets anchored with nanoparticles with super-high surface area were synthesized via the hydrothermal self-assembly method. Investigations found that the nanoparticles are uniformly decorated on the surface of graphene nanosheets and the heterocomposites successfully shift the absorption edge from the UV range for pure nanoparticles to a visible range. Photocatalytic investigations show that the heterostructures possessing enhanced photocatalytic ability for the Rhodamine B degradation under visible light irradiation. The visible light photocatalytic performance can be attributed to the synergetic effect of graphene and dye molecules. The superior photocatalytic efficiency is ascribed to the large specific surface area of the heterocomposites and the superior electronic characteristics of graphene, which greatly restrain the self-radiative recombination of photogenerated electron–hole pairs.