An image processing apparatus capable of reducing time taken to retrieve a specific image including a specific object area from a plurality of images, even when an image is newly added or a face dictionary is updated. A CPU of the apparatus determines whether or not object search information indicating the image is a candidate image as a candidate of the specific image exists in management information. When the object search information does not exist, the CPU refers to an object dictionary in which feature value data of an objects are registered, and compares feature value data of an object detected from a image and the feature value data of the object dictionary to thereby retrieve candidate images. When the object search information exists, the CPU retrieves candidate images based on the object search information.