Electrochemical sensors integrating hybrid nanostructured platforms are a promising alternative to conventional detection techniques for addressing highly relevant challenges of heavy metal determination in the environment. Hybrid nanocomposites based on graphene derivatives and inorganic nanoparticles (NPs) are ideal candidates as active materials for detecting heavy metals, as they merge the relevant physico-chemical properties of both the components, finally leading to a rapid and sensitive current response. In this work, a hybrid nanocomposite formed of reduced graphene oxide (RGO) sheets, surface functionalized by π-π interactions with 1-pyrene carboxylic acid (PCA), and decorated in situ by Au NPs, was synthesized by using a colloidal route. The hybrid nanocomposite was characterized by cyclic voltammetry and electrochemical impedance spectroscopy with respect to the corresponding single components, both bare and deposited as a layer-by-layer junction onto the electrode. The results demonstrated the high electrochemical activity of the hybrid nanocomposite with respect to the single components, highlighting the crucial role of the nanostructured surface morphology of the electrode and the PCA coupling agent at the NPs-RGO interphase in enhancing the nanocomposite electroactivity. Finally, the Au NP-decorated PCA-RGO sheets were tested by anodic stripping voltammetry of As(III) ion—a particularly relevant analyte among heavy metal ions—in order to assess the sensing ability of the nanocomposite material with respect to its single components. The nanocomposite has been found to present a sensitivity higher than that characterizing the bare components, with LODs complying with the directives established by the U.S. EPA and in line with those reported for state-of-the-art electrochemical sensors based on other Au-graphene nanocomposites.