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.