In this correspondence, we propose a novel method to extract illumination insensitive features for face recognition under varying lighting called the gradient faces. Theoretical analysis shows gradient faces is an illumination insensitive measure, and robust to different illumination, including uncontrolled, natural lighting. In addition, gradient faces is derived from the image gradient domain such that it can discover underlying inherent structure of face images since the gradient domain explicitly considers the relationships between neighboring pixel points. Therefore, gradient faces has more discriminating power than the illumination insensitive measure extracted from the pixel domain. Recognition rates of 99.83% achieved on PIE database of 68 subjects, 98.96% achieved on Yale B of ten subjects, and 95.61% achieved on Outdoor database of 132 subjects under uncontrolled natural lighting conditions show that gradient faces is an effective method for face recognition under varying illumination. Furthermore, the experimental results on Yale database validate that gradient faces is also insensitive to image noise and object artifacts (such as facial expressions).