Graphene paper has diverse applications in printed circuit board electronics, bioassays, 3D cell culture, and biosensing. Although development of nanometal-graphene hybrid composites is commonplace in the sensing literature, to date there are only a few examples of nanometal-decorated graphene paper for use in biosensing. In this manuscript, we demonstrate the synthesis and application of Pt nano cauliflower-functionalized graphene paper for use in electrochemical biosensing of small molecules (glucose, acetone, methanol) or detection of pathogenic bacteria (Escherichia coli O157:H7). Raman spectroscopy, scanning electron microscopy and energy dispersive spectroscopy were used to show that graphene oxide deposited on nanocellulose crystals was partially reduced by both thermal and chemical treatment. Fractal platinum nanostructures were formed on the reduced graphene oxide paper, producing a conductive paper with an extremely high electroactive surface area, confirmed by cyclic voltammetry and electrochemical impedance spectroscopy. To show the broad applicability of the material, the platinum surface was functionalized with three different biomaterials: 1) glucose oxidase (via chitosan encapsulation); 2) a DNA aptamer (via covalent linking), or 3) a chemosensory protein (via his linking). We demonstrate the application of this device for point of care biosensing. The detection limit for both glucose (0.08 ± 0.02 μM) and E. coli O157:H7 (1.3 ± 0.1 CFU mL_-1) were competitive with, or superior to, previously reported devices in the biosensing literature. The response time (6 sec for glucose and 10 min 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.