Recent studies show that pattern-recognition-based transient stability assessment (PRTSA) is a promising approach for predicting the transient stability status of power systems. However, many of the current well-known PRTSA methods suffer from excessive training time and complex tuning of parameters, resulting in inefficiency for real-time implementation and lacking the online model updating ability. In this paper, a novel PRTSA approach based on an ensemble of OS-extreme learning machine (EOSELM) with binary Jaya (BinJaya)-based feature selection is proposed with the use of phasor measurement units (PMUs) data. After briefly describing the principles of OS-ELM, an EOS-ELM-based PRTSA model is built to predict the post-fault transient stability status of power systems in real time by integrating OS-ELM and an online boosting algorithm, respectively, as a weak classifier and an ensemble learning algorithm. Furthermore, a BinJaya-based feature selection approach is put forward for selecting an optimal feature subset from the entire feature space constituted by a group of system-level classification features extracted from PMU data. The application results on the IEEE 39-bus system and a real provincial system show that the proposal has superior computation speed and prediction accuracy than other state-of-the-art sequential learning algorithms. In addition, without sacrificing the classification performance, the dimension of the input space has been reduced to about one-third of its initial value.