Fast, reliable and selective detection of microorganisms is of uttermost importance in clinical analysis, but also in food and water quality monitoring. In this study, we report on the construction of an immunosensor for sensitive and selective electrochemical detection of uropathogenic Escherichia coli (E. coli) UTI89 bacteria in aqueous and serum samples. We took benefit of electrophoretic deposition (EPD) to prepare, in a simple, controllable and cost effective way, gold electrodes modified with thin active layers of reduced graphene oxide/polyethylenimine (rGO/PEI). While rGO exhibits high surface area and favourable electrochemical properties, the presence of abundant NH2 groups on PEI offers a plethora of opportunities for the sensor’s surface functionalization. To achieve selectivity of detection, the electrode surface was covalently modified with anti-fimbrial E. coli antibodies via amide bond formation. To minimize non-specific adsorption, the immunosensor was additionally modified with pyrene-polyethyleneglycol (pyrene-PEG) moieties prior to antibody immobilization. The detection of E. coli was based on the restriction of electron transfer of a redox mediator, in our case potassium ferrocyanide, to the rGO/PEI modified electrical transducer due to the formation of an immune complex. The developed immunosensor displayed a sigmoidal shape with a linear range of 1 × 101–1 × 104 cfu mL−1 (R2 = 0.995) according to i(μA) = −16.66–20.5 × log[E. coli] (cfu mL−1) and a detection limit of 10 cfu mL−1. Additionally, the sensor performed well both in aqueous, serum and urine media, which is essential for its potential use for clinical diagnosis of pathogenic diseases. Selectivity studies showed that the immunosensor was able to discriminate between E. coli UTI89 wild-type strain and UTI89 Δfim, without fim operon.