A method and apparatus with an adaptively updated enrollment database (DB) are provided. A method with an adaptively updated enrollment database (DB) includes extracting an input feature vector from an input image, determining whether the input feature vector is included in a changeable enrollment range, with the changeable enrollment range being determined based on a threshold distance from each of plural enrolled feature vectors in the enrollment DB, and with the enrolled feature vectors corresponding to enrolled images, determining whether to enroll the input feature vector in the enrollment DB in response to the input feature vector being determined as being included in the changeable enrollment range, and in response to a result of the determining of whether to enroll the input feature vector being to enroll the input feature vector, selectively enrolling the input feature vector in the enrollment DB.