This paper develops a new approach to forecast natural gas consumption via ensembles. It combines Bootstrap Aggregation (Bagging), univariate time series forecasting methods and modified regularization routines. A new variant of Bagging is introduced, which uses Maximum Entropy Bootstrap (MEB) and a modified regularization routine that ensures that the data generating process is kept in the ensemble. Monthly natural gas consumption time series from 18 European countries are considered. A comparative, out-of-sample evaluation is conducted up to 12 steps (a year) ahead, using a comprehensive set of competing forecasting approaches. These range from statistical benchmarks to machine learning methods and state-of-the-art ensembles. Several performance (accuracy) metrics are used, and a sensitivity analysis is undertaken. Overall, the new variant of Bagging is flexible, reliable, and outperforms well-established approaches. Consequently, it is suitable to support decision making in the energy and other sectors. • A novel ensemble approach to natural gas demand forecasting is proposed. • Machine Learning and Statistics are combined to tailor time series characteristics. • Monthly data from 18 EU markets are used to assess forecasting performance. • The approach is shown to be suitable to support decision making in the energy sector.