The effect of synthesized nanostructures, including graphene oxide, chemically reduced graphene oxide with sodium dodecyl sulfate (SDS), chemically reduced graphene oxide with polyvinylpyrrolidone, and multi-walled carbon nanotubes, on the kinetics of methane hydrate formation was investigated in this work. The experiments were carried out at a pressure of 4.5 MPa and a temperature of 0 °C in a batch reactor. By adding nanostructures, the induction time decreases, and the shortest induction time appeares at certain concentrations of reduced graphene oxide with SDS and graphene oxide, that is, at a concentration of 360 ppm for reduced graphene oxide with SDS and 180 ppm for graphene oxide, with a 98% decrease in induction time compared to that in pure water. Moreover, utilization of carbon nanostructures increases the amount and the rate of methane consumed during the hydrate formation process. Utilization of multi-walled carbon nanotubes with a concentration of 90 ppm showes the highest amount of methane consumption. The amount of methane consumption increases by 173% in comparison with that in pure water. The addition of carbon nanostructures does not change the storage capacity of methane hydrate in the hydrate formation process, while the percentage of water conversion to hydrate in the presence of carbon nanotubes increases considerably, the greatest value of which occurres at a 90 ppm concentration of carbon nanotubes, that is, a 253% increase in the presence of carbon nanotubes compared to that of pure water.