In accordance with the regulations of the Energy Agency of the Republic of Slovenia, each natural gas supplier regulates and determines the charges for the differences between the ordered (predicted) and the actually supplied quantities of natural gas. Yearly charges for these differences represent up to 2% of supplied natural gas costs. All the natural gas users, especially industry, have huge problems finding the proper method for efficient natural gas consumption prediction and, consequently, the decreasing of mentioned costs. In this study, prediction of the natural gas consumption in Štore Steel Ltd. (steel plant) is presented. On the basis of production data, several models for natural gas consumption have been developed using linear regression, genetic programming and artificial neural network methods. The genetic programming approach outperformed linear regression and artificial neural networks.