The mildly acidic and oxidative nature of graphene oxide, with its large surface area available for catalytic activity, has been explored in aromatic nuclear bromination chemistry for the first time. The versatile catalytic activity of graphene oxide (GO) has been used to selectively and rapidly brominate anilines and phenols in water. The best results were obtained at ambient temperatures using molecular bromine in a protocol promoted by oxidative bromination catalyzed by GO; these transformations proceeded with 100% atom economy with respect to bromine and high selectivities for the tribromoanilines and -phenols. Reduced graphene oxide (r-GO) was observed to form after the second recycle (third use) of GO. This technique is also effective with N-bromosuccinimide (NBS) as the brominating reagent. In the case of NBS, reactions were instantaneous and the GO displayed excellent recyclability without any loss of activity over several cycles.