This work describes a simple method for the fabrication of an enzymatic electrode with high sensitivity to oxygen and good performance when applied as biocathode. Pencil graphite electrodes (PGE) were chosen as disposable transducers given their availability and good electrochemical response. After electrochemical characterization regarding hardness and surface pre-treatment suited modification with carbon-based nanostructures, namely with reduced graphene, MWCNT and carbon black for optimal performance was proceeded. The bioelectrode was finally assembled through immobilization of bilirubin oxidase (BOx) lashed on the modified surface of MWCNT via π-π stacking and amide bond functionalization. The high sensitivity towards dissolved oxygen of 648 ± 51 µA mM-1 cm-2, and a LOD of 1.7 µM, was achieved for the PGE with surface previously modified with reduced graphene (rGO), almost the double registered for direct anchorage on the bare PGE surface. Polarization curves resulted in an open circuit potential (OCP) of 1.68 V (vs Zn electrode) and generated a maximum current density of about 650 μA cm-2 in O2 saturated solution.