The exsiting example-based super-resolution algorithms of face image adopt global search, which causes the problems of non-local mismatch and poor visual effect of image restoration. A new matching and learning-based face image super-resolution restoration algorithm is proposed. A pre-classification process of input image is applied to get a sub-sample library from the image library, and the corresponding feature images are created. In the matching process, two new search strategies for different face images are used, which consider the similarity and consistency between image patches and make the recovered image look more coherent and natural. Experimental results show that the proposed algorithm synthesizes high-resolution faces with better visual effect and obtains higher values of the average of Peak Signal-to-Noise Ratios(PSNR) when compared with other methods.