In neighbor embedding based face hallucination, the training and reconstruction processes are performed in the feature space, thus the feature selection is important. In addition, there is no constraint specified for the signs of the weights generated in neighbor embedding algorithm, which leads to over-fitting and degradation of the recovered face images. Considering the importance of feature selection and the constraints of weights, a novel neighbor embedding face hallucination method is proposed based on non-negative weights and Two-Dimensional Principal Component Analysis (2D-PCA) features. First, the face images are partitioned into patches, and the local visual primitives are obtained by k-means clustering algorithm. The face image patches are classified with the local visual primitives generated before. Second, the feature of face image patches is captured with 2D-PCA, and the low and high dictionary is established. Finally, a novel non-negative weights solution method is used to obtain the weights. The experiment results show that the weights computed by the proposed method have more stable behavior and obviously less over-fitting phenomenon, furthermore, the recovery face images have better subjective and objective quality.