Accurate wind speed prediction is critical for many tasks, especially for air pollution modelling. Data-driven approaches are particularly interesting but the stochastic nature of wind renders prediction tasks difficult. Therefore, a combination of methods could be useful to obtain better results. To overcome this difficulty, a hybrid wind speed forecasting approach is proposed in this work. The Bay of Algeciras, Spain, was used as a case study, and the database was collected from a weather monitoring station. The study consists of combining a pre-processing method, the empirical mode decomposition (EMD), an information-based method, the permutation entropy (PE), and a machine learning technique (artificial neural networks, ANNs), using an ensemble learning methodology. Different prediction horizons were considered: ph-hours (ph = 1, 2, 8, 24) ahead and 8-h and 24-h average. The introduction of PE significantly reduces the computational cost and the predictive risk in comparison with traditional EMD methodology, by reducing the number of the decomposed components to be predicted. Moreover, the experimental results demonstrated that the EMD–PE–ANN approach outperforms the prediction performance of the single ANN models in all the prediction horizons tested. The EMD–PE–ANN model is capable to achieve a correlation coefficient of 0.981 and 0.807 for short-term (1 h) and medium-term (24 h) predictions, respectively, significantly overcoming those obtained by a single ANN model (0.929 and 0.503). These results show that the proposed model reaches significant improvements when the prediction horizon increases, where forecasting models tend to worsen their prediction performance. Therefore, the proposed EMD–PE–ANN approach may become a powerful tool for wind speed forecasting.