Self-sustained locomotion by virtue of an internalized chemical reaction is a characteristic feature of living systems and has inspired researchers to develop such self-moving biomimetic systems. Here, we harness a self-oscillating Belousov-Zhabotinsky (BZ) reaction, a well-known chemical oscillator, with enhanced kinetics by virtue of our graphene-based catalytic mats, to elucidate the spontaneous locomotion of BZ reaction droplets. Specifically, our nanocatalysts comprise ruthenium nanoparticle decorations on graphene oxide, reduced graphene oxide, and graphene nanosheets, thereby creating 0D-2D heterostructures. We demonstrate that when these nanocatalyzed droplets of the BZ reaction are placed in an oil-surfactant medium, they exhibit a macroscopic translatory motion at the velocities of few millimeters per second. This motion is brought about by the combination of enhanced kinetics of the BZ reaction and the Marangoni effect. Our investigations reveal that the velocity of locomotion increases with the electrical conductivity of our nanocomposites. Moreover, we also show that the positive feedback generated by the reaction-diffusion phenomena results in an asymmetric distribution of surface tension that, in turn, facilitates the self-propelled motion of the BZ droplets. Finally, we explore a system of multiple nanocatalyzed BZ droplets and reveal a variety of motions caused by their mutual interactions. Our findings suggest that through the use of 0D-2D hybrid nanomaterials, it is possible to design fast-moving self-propelled synthetic objects for a variety of biomimetic applications.