Transmission of natural gas with methane as the main constituent has been a subject of interest to industrial companies. Predicting hydrate formation conditions is important to prevent formation of methane hydrate in gas pipeline. Also, attention has been taken to account for capture and storage of pure methane. In this paper, a comprehensive comparison is performed between empirical correlations and different equation of state in van der Waals Platteeuw (VdW-P) thermodynamic model to determine the most accurate method of hydrate formation condition of methane. In addition, a novel, simple and accurate correlation is developed to predict methane hydrate formation temperature using genetic programming. Error analysis on a wide range of experimental data indicates that the new proposed correlation is superior over existing correlations and all VdW-P models with R2 = 0.999.