We demonstrate the first report of graphene paper functionalized with fractal platinum nanocauliflower for use in electrochemical biosensing of small molecules (glucose) or detection of pathogenic bacteria (Escherichia coli O157:H7). Raman spectroscopy, scanning electron microscopy and energy dispersive spectroscopy show that graphene oxide-coated nanocellulose was partially reduced by both thermal treatment, and further reduced by chemical treatment (ascorbic acid). Fractal nanoplatinum with cauliflower-like morphology was formed on the reduced graphene oxide paper using pulsed sonoelectrodeposition, producing a conductive paper with an extremely high electroactive surface area (0.29±0.13cm2), confirmed by cyclic voltammetry and electrochemical impedance spectroscopy. The platinum surface was functionalized with either glucose oxidase (via chitosan encapsulation) or a RNA aptamer (via covalent linking) for demonstration as a point of care biosensor. The detection limit for both glucose (0.08±0.02μM) and E. coli O157:H7 (≈4 CFUmL−1) were competitive with, or superior to, previously reported devices in the biosensing literature. The response time (6s for glucose and 12min for E. coli) were also similar to silicon biochip and commercial electrode sensors. The results demonstrate that the nanocellulose-graphene-nanoplatinum material is an excellent paper-based platform for development of electrochemical biosensors targeting small molecules or whole cells for use in point of care biosensing.