We describe the use of a nanocomposite consisting of graphene and β-cyclodextrin (β-CD) which was used to modify a glassy carbon electrode (GCE) to serve as a matrix for immobilization of hemoglobin (Hb). The composite was characterized by scanning electron microscopy, UV-vis and FTIR spectroscopy. The modified electrode displays an enhanced and well-defined quasi reversible peaks for the heme protein at a formal potential of −0.284 V (vs. Ag/AgCl). The direct electrochemistry of Hb is strongly enhanced at this modified electrode compared to electrodes not modified with graphene or β-CD. The heterogeneous electron transfer rate constant (Ks) is 3.18 ± 0.7 s−1 which indicates fast electron transfer. The biosensor exhibits excellent electrocatalytic activity towards the reduction of bromate, with a linear amperometric response in the 0.1 to 176.6 μM concentration range at a working voltage of −0.33 V. The sensitivity is 3.39 μA μM−1 cm−2, and the detection limit is 33 nM. The biosensor is fast, selective, well repeatable and reproducible, and therefore represents a viable platform for sensing bromate in aqueous samples.