(1) Background: Forecasting of energy consumption demand is a crucial task linked directly with the economy of every country all over the world. Accurate natural gas consumption forecasting allows policy makers to formulate natural gas supply planning and apply the right strategic policies in this direction. In order to develop a real accurate natural gas (NG) prediction model for Greece, we examine the application of neuro-fuzzy models, which have recently shown significant contribution in the energy domain. (2) Methods: The adaptive neuro-fuzzy inference system (ANFIS) is a flexible and easy to use modeling method in the area of soft computing, integrating both neural networks and fuzzy logic principles. The present study aims to develop a proper ANFIS architecture for time series modeling and prediction of day-ahead natural gas demand. (3) Results: An efficient and fast ANFIS architecture is built based on neuro-fuzzy exploration performance for energy demand prediction using historical data of natural gas consumption, achieving a high prediction accuracy. The best performing ANFIS method is also compared with other well-known artificial neural networks (ANNs), soft computing methods such as fuzzy cognitive map (FCM) and their hybrid combination architectures for natural gas prediction, reported in the literature, to further assess its prediction performance. The conducted analysis reveals that the mean absolute percentage error (MAPE) of the proposed ANFIS architecture results is less than 20% in almost all the examined Greek cities, outperforming ANNs, FCMs and their hybrid combination; and (4) Conclusions: The produced results reveal an improved prediction efficacy of the proposed ANFIS-based approach for the examined natural gas case study in Greece, thus providing a fast and efficient tool for utterly accurate predictions of future short-term natural gas demand.