Using the empirical mode decomposition (EMD) and fast ensemble empirical mode decomposition (FEEMD), respectively, a nonstationary downburst wind velocity sample can be decomposed into a series of stationary sequence sets, namely, intrinsic mode functions. Extreme learning machines based on EMD and FEEMD, referred to as the EMD-ELM and FEEMD-ELM, are proposed to forecast the training and testing sets, both partitioned to stationary sequence sets. Meanwhile, combining EMD and FEEMD with a least squares support vector machine (SVM) based on particle swarm optimization, EMD-PSO-LSSVM and FEEMD-PSO-LSSVM algorithms are obtained. Comparison of these four prediction algorithms shows that EMD-ELM and FEEMD-ELM are more accurate and efficient in predicting nonstationary downburst wind velocity, while FEEMD-ELM is the best.