In this correspondence, we propose a novel method to extract illumination insensitive features for face recognition under varying lighting called the Gradientfaces. Theoretical analysis shows Gradientfaces is an illumination insensitive measure, and robust to different illumination, including uncontrolled, natural lighting. In addition, Gradientfaces 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, Gradientfaces 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 Gradientfaces is an effective method for face recognition under varying illumination. Furthermore, the experimental results on Yale database validate that Gradientfaces is also insensitive to image noise and object artifacts (such as facial expressions). © 2009 IEEE.