Face recognition is a challenging problem due to different illuminations, poses, facial expressions, and occlusions. In this paper, a new robust face recognition method is proposed based on the color and edge orientation difference histogram. Firstly, the color and edge orientation difference histogram is extracted using color, color difference, edge orientation, and edge orientation difference of the face image. Then the backward feature selection is employed in order to reduce the number of features. Finally, the Canberra measure is used to assess the similarity between the images. The color and edge orientation difference histogram shows the color and edge orientation difference between two neighboring pixels. This histogram is effective for face recognition due to the different skin colors and different edge orientations of the face image, which leads to a different light reflection. The proposed method is evaluated on the Yale and ORL face datasets. These datasets consist of gray-scale face images under different illuminations, poses, facial expressions, and occlusions. The recognition rate over the Yale and ORL datasets is achieved to be 100% and 98.75%, respectively. The experimental results demonstrate that the proposed method outperforms the existing methods in face recognition.