For complicated classification problems, the standard Support Vector Machine (SVM) is likely to be complex and thus the classification efficiency is low. In this paper, we propose a new efficient SVM (eSVM), which is based on the idea of minimizing the margin of misclassified samples. Compared with the conventional SVM, the eSVM is defined on fewer support vectors and thus can achieve much faster classification speed and comparable or even higher classification accuracy. We then present a real-time accurate eye localization system using the eSVM together with color information and 2D Haar wavelet features. Experiments on some public data sets show that (i) the eSVM significantly improves the efficiency of the standard SVM without sacrificing its accuracy and (ii) the eye localization system has real-time speed and higher detection accuracy than some state-of-the-art approaches.