An image processing apparatus capable of improving the usability in search by, for a person presumed to be difficult to be misidentified, improving the frequency of identifying the person. When calculated degree of similarity is equal to or greater than a threshold, it is identified that a face of the person corresponds to a face of any one of registered persons. The threshold is set to a second value greater than a first value, for the face of one of the registered persons who has not been identified when starting recording of the image, and the threshold is set to a third value between the first value and the second value, for the face of one of the registered persons who is already identified when starting the recording of the image, after the recording of the shot image to the nonvolatile recording medium is started.