Traditional face alignment based on machine learning usually tracks the localizations of facial landmarks employing a static model trained offline where all of the training data are available in advance. When new training samples arrive, the static model must be retrained from scratch, which is excessively time-consuming and memory-consuming. It results in the limitation of its performance on sequential images with extensive variations. Therefore, the most critical and challenging aspect in this field is how to enhance the predictive capability of pretrained model incrementally. To that end, a fast and accurate online learning algorithm for face alignment is proposed. Particularly, extreme learning machine (ELM) is incorporated into a parallel cascaded regression (CR) framework, which we coin parallel cascade regression based on extreme learning machine (CRELM). The proposed model can be fast updated in an incremental way. It has a stronger prediction capability than conventional CR methods. The experimental results demonstrate that the proposed model is more accurate and efficient on still images or videos compared with the recent state-of-the-art approaches.