Cyclodextrins (CDs) are oligosaccharides composed of six, seven, or eight glucose units (alpha-, beta-, or gamma-CD, respectively), which are toroidal in shape with a hydrophobic inner cavity and a hydrophilic exterior. These interesting characteristics can enable them to bind selectively various organic, inorganic and biological guest molecules into their cavities to form stable host-guest inclusion complexes or nanostructured supramolecular assemblies in their hydrophobic cavity. On the other hand graphene nanosheet (GN), a rising-star material, holds great promise for potential applications in many technological fields due to its high surface areas, low cost, and high conductivity. If GNs are modified with CDs, it is possible to obtain new materials simultaneously possessing unique properties of GNs and cyclodextrins through combining their individual obvious advantages. In this article, we demonstrate for the first time a simple wet-chemical strategy for the preparation of CD-graphene organic-inorganic hybrid nanosheets (CD-GNs), which exhibited high solubility and stability in polar solvent. The obtained CD-GNs were characterized by UV-vis spectroscopy, static contact angle measurement, thermogravimetric analysis, X-ray photoelectron spectroscopy, Fourier transform infrared spectroscopy, Raman spectroscopy, atomic force microscopy, transmission electron microscopy, and electrochemical impedance spectroscopy, which confirmed that CD had been effectively functionalized on the surface of GNs. Furthermore, the formation mechanism of CD-GNs was also discussed. Interestingly, GNs here could load a number of CD molecules, which was very important for greatly enhancing the supramolecular function of CDs. Electrochemical results obviously reveal that CD-graphene organic-inorganic hybrid nanosheets could exhibit very high supramolecular recognition and enrichment capability and show much higher electrochemical response toward eight probe molecules (biomolecules and drugs) than unmodified GNs and carbon nanotubes, which is probably caused by the synergetic effects from GNs (high conductivity and high surface area) and CD molecules (host-guest recognition and enrichment).