In this communication we present a potentiometric aptasensor based on chemically modified graphene (transducer layer of the aptasensor) and aptamers (sensing layer). Graphene oxide (GO) and reduced graphene oxide (RGO) are the basis for the construction of two versions of the aptasensor for the detection of a challenging living organism such as Staphylococcus aureus. In these two versions, DNA aptamers are either covalently (in the GO case) or non-covalently (in the RGO case) attached to the transducer layer. In both cases we are able to selectively detect a single CFU/mL of S. aureus in an assay close to real time, although the noise level associated to the aptasensors made with RGO is lower than the ones made with GO. These new aptasensors, that show a high selectivity, are characterized by the simplicity of the technique and the materials used for their construction while offering ultra-low detection limits in very short time responses in the detection of microorganisms.