The potentiality prediction of enhanced oil recovery (EOR) is the basis of EOR potentiality analysis as well as the robust guarantee of the reliability of analysis results. In the light of statistical learning theory, establishing an EOR predictive model substantially falls within the problem of function approximation. According to Vapnik's structural risk minimization principle, one should improve the generalization ability of learning machine, that is, a small error from an effective training set can guarantee a small error for the corresponding independent testing set. The up-to-date results from studies on statistical theory in recent decades even recent years are firstly applied to EOR potentiality analysis. The applications of group method of data handling (GMDH), Improved BP artificial neural network, and support vector machine (SVM) are discussed. The comparison of the results from three methods indicates that SVM can pay more attention to both the universality and extendibility of a model when the samples are very limited, which shows a good prospect of its application. A method used to generate a set of sample theoretically is developed in this research by combining quadrate designing, reservoir simulation, and economical evaluation.