Graphene and its nanocomposites are showing excellent potential in improving the catalytic performances of different materials. However, the synthetic protocol and its form, such as graphene oxide (GRO) or highly reduced graphene oxide (HRG), influence the catalytic efficiencies. Here, we present, a facile synthesis of graphene oxide (GRO) and ZrOx-MnCO3-based nanocomposites [(1%)ZrOx–MnCO3/(x%)GRO] and their outcome as an oxidation catalyst for alcohol oxidation under mild conditions using O2 as a clean oxidant. The ZrOx–MnCO3/GRO catalyst prepared by incorporating GRO to pre-calcined ZrOx-MnCO3 using ball milling showed remarkable enhancement in the catalytic activities as compared to pristine ZrOx–MnCO3, ZrOx–MnCO3 supported on HRG or ZrOx–MnCO3/GRO prepared by in-situ growth of ZrOx–MnCO3 onto GRO followed by calcination. The catalyst with composition (1%)ZrOx–MnCO3/(1%)GRO exhibited superior specific activity (57.1 mmol/g·h) with complete conversion and >99% selectivity of the product within a short period of time (7 min) and at a relatively lower temperature (100 °C). The catalyst could be recycled at least five times with a negligible decrease in efficiency and selectivity. The catalytic study was extended to different aromatic as well as aliphatic alcohols under optimized conditions, which confirmed the efficiency and selectivity of the catalyst.