There is an increasing need for the rapid detection of S. aureus owing to the health concerns it raises worldwide. Electrochemical detection methods have proved to be rapid and capable of offering Point-Of-Care diagnosis. Recently, graphene-based materials have emerged as most promising nanomaterials for electrochemical analysis. They have shown improved sensitivity and stability when used as transducer matrices in electrochemical sensing. The latest entrant in this class of materials is Graphene Quantum Dots (GQDs) which, apart from their optical properties possess excellent electrical conductivity and electro-catalytic properties. In this contribution, we explored GQD as electrochemical probe in a sandwich immunoassay designed to detect pathogenic strain of S. aureus. Our results show that GQDs, when used as immuno-labels, improved the sensitivity of the assay by more than 100%. The limit of detection (LOD) was less than 1 CFU/ mL. Moreover, it offers rapid detection of pathogens in less than an hour.