An information processing apparatus comprising: first acquisition means configured to acquire a first feature from a face image of a search person in a search source image which is at least one of a plurality of video images, wherein the first feature is a feature obtained from a face image, and wherein the first feature of at least one image among the plurality of video images is stored in a storage; first search means (213, 816) configured to search for the search person from the plurality of video images using the first feature acquired by the first acquisition means from the face image of the search person in the search source image as a query, to obtain a first search result image (501, 504), which is at least one of the plurality of video images, with a similarity between the first feature stored in the storage and the first feature acquired by the first acquisition means from the face image of the search person in the search source image being equal to or higher than a predetermined threshold; second acquisition means (215, 815) configured to acquire a second feature from a human body image of the search person in the first search result image, wherein the second feature is a feature obtained from a human body image, and wherein the second feature of at least one image among the plurality of video images is stored in the storage; and second search means (216, 813) configured to search, using the second feature of the search person in the first search result image acquired by the second acquisition means as a query, for the search person from the plurality of video images, to obtain a second search result image (502, 503, 505) with a similarity between the second feature stored in the storage and the second feature of the search person in the first search result image acquired by the second acquisition means being equal to or higher than a predetermined threshold. first acquisition means configured to acquire a first feature from a face image of a search person in a search source image which is at least one of a plurality of video images, wherein the first feature is a feature obtained from a face image, and wherein the first feature of at least one image among the plurality of video images is stored in a storage; first search means (213, 816) configured to search for the search person from the plurality of video images using the first feature acquired by the first acquisition means from the face image of the search person in the search source image as a query, to obtain a first search result image (501, 504), which is at least one of the plurality of video images, with a similarity between the first feature stored in the storage and the first feature acquired by the first acquisition means from the face image of the search person in the search source image being equal to or higher than a predetermined threshold; second acquisition means (215, 815) configured to acquire a second feature from a human body image of the search person in the first search result image, wherein the second feature is a feature obtained from a human body image, and wherein the second feature of at least one image among the plurality of video images is stored in the storage; and second search means (216, 813) configured to search, using the second feature of the search person in the first search result image acquired by the second acquisition means as a query, for the search person from the plurality of video images, to obtain a second search result image (502, 503, 505) with a similarity between the second feature stored in the storage and the second feature of the search person in the first search result image acquired by the second acquisition means being equal to or higher than a predetermined threshold.