This paper presents a novel approach for Voltage Stability Margin (VSM) estimation that combines a Kernel Extreme Learning Machine (KELM) with a Mean-Variance Mapping Optimization (MVMO) algorithm. Since the performance of a KELM depends on a proper parameter selection, the MVMO is used to optimize such task. In the proposed MVMO-KELM model the inputs and output are the magnitudes of voltage phasors and the VSM index, respectively. A Monte Carlo simulation was implemented to build a data base for the training and validation of the model. The data base considers different operative scenarios for three type of customers (residential commercial and industrial) as well as N-1 contingencies. The proposed MVMO-KELM model was validated with the IEEE 39 bus power system comparing its performance with a support vector machine (SVM) and an Artificial Neural Network (ANN) approach. Results evidenced a better performance of the proposed MVMO-KELM model when compared to such techniques. Furthermore, the higher robustness of the MVMO-KELM was also evidenced when considering noise in the input data.