Classic forecasting methods of natural gas consumption extrapolate trends from the past to subsequent periods of time. The paper presents a different approach that uses analogues to create long-term forecasts of the annual natural gas consumption. The energy intensity (energy consumption per dollar of Gross Domestic Product—GDP) and gas share in energy mix in some countries, usually more developed, are the starting point for forecasts of other countries in the later period. The novelty of the approach arises in the use of cluster analysis to create similar groups of countries and periods based on two indicators: energy intensity of GDP and share of natural gas consumption in the energy mix, and then the use of fuzzy decision trees for classifying countries in different years into clusters based on several other economic indicators. The final long-term forecasts are obtained with the use of fuzzy decision trees by combining the forecasts for different fuzzy sets made by the method of relative chain increments. The forecast accuracy of our method is higher than that of other benchmark methods. The proposed method may be an excellent tool for forecasting long-term territorial natural gas consumption for any administrative unit.