Since wind has an intrinsically complex and stochastic nature, accurate wind power prediction is necessary for the safety and economics of wind energy utilization. Aiming at the prediction of very short-term wind power time series, a new optimized kernel extreme learning machine (O-KELM) method with evolutionary computation strategy is proposed on the basis of single-hidden layer feedforward neural networks. In comparison to the extreme learning machine (ELM) method, the number of the hidden layer nodes need not be given, and the unknown nonlinear feature mapping of the hidden layer is represented with a kernel function. In addition, the output weights of the networks can also be analytically determined by using regularization least square algorithm, hence the kernel extreme learning machine (KELM) method provides better generalization performance at a much faster learning speed. In the O-KELM, the structure and the parameters of the KELM are optimized by using three different optimization algorithms, i.e., genetic algorithm (GA), differential evolution (DE), and simulated annerling (SA), meanwhile, the output weights are obtained by a least squares algorithm just the same as by the ELM, but using Tikhonovs regularization in order to further improve the performance of the O-KELM. The utilized optimization algorithms of the O-KELM are respectively used to select the set of input variables, regularization coefficient as well as hyperparameter of kernel function. The proposed method is first applied to the direct six-step prediction for Mackey-Glass chaotic time series, under the same condition as the existing optimized ELM method. From the analysis of the simulation results it can be verified that the prediction accuracy of the proposed O-KELM method is increased by about one order of magnitude over that of the optimized ELM method. Furthermore, the DE-KELM algorithm can achieve the lowest root mean square error (RMSE). The O-KELM method is then applied to real-world wind power prediction instance, i.e., the Western Dataset from NERL. The 10-minute ahead single-step prediction as well as 20-minute ahead, 30-minute ahead, 40-minute ahead multi-step prediction for wind power time series are respectively implemented to evaluate the O-KELM method. Experimental results of each of the short-term wind power time series predictions at different time horizons confirm that the proposed O-KELM method tends to have better prediction accuracy than the optimized ELM method. Moreover, the GA-KELM algorithm outperforms other two O-KELM algorithms at future 10-minute, 20-minute, 40-minute ahead prediction in terms of the RMSE value. The DE-KELM algorithm outperforms other algorithms at future 30-minute ahead prediction in terms of the normalized mean square error (NMSE) and the RMSE value. The results from these applications demonstrate the effectiveness and feasibility of the proposed O-KLEM method. Therefore, the O-KELM method has a potential future in the field of wind power prediction.