This paper presents a novel framework to localize in a photograph prominent irregularities in facial skin, in particular nevi (moles, birthmarks). Their characteristic configuration over a face is used to encode the person's identity independent of pose and illumination. This approach extends conventional recognition methods, which usually disregard such small scale variations and thereby miss potentially highly discriminative features. Our system detects potential nevi with a very sensitive multi scale template matching procedure. The candidate points are filtered according to their discriminative potential, using two complementary methods. One is a novel skin segmentation scheme based on gray scale texture analysis that we developed to perform outlier detection in the face. Unlike most other skin detection/segmentation methods it does not require color input. The second is a local saliency measure to express a point's uniqueness and confidence taking the neighborhood's texture characteristics into account. We experimentally evaluate the suitability of the detected features for identification under different poses and illumination on a subset of the FERET face database.