In this study, we report a novel supramolecular polyaniline-β-cyclodextrin-graphene nanosheet (PANI-β-CD-GNS) composite through in situ polymerization of aniline in presence of β-CD-GNS. The microstructure and morphology of the PANI-β-CD-GNS are characterized by various techniques. The enhanced radical cation stability of the composite is confirmed by electron paramagnetic resonance (EPR) spectroscopy. PANI-β-CD-GNS exhibits superior electrochemical properties than PANI-GNS such as a specific capacitance of 1071 F g−1 at 2 mV s−1, good long term cycling stability with 91.8% capacitance retention after 5000 cycles at 5 A g−1 current density. It is observed that high radical cation stability of PANI-β-CD-GNS showed significant impact on its electrochemical properties. The results of electrochemical analysis clearly indicate the potential usability of this material as novel organic radical supercapacitors for high-performance energy storage devices.