An object tracking apparatus is configured to execute a tracking process, a prediction process, an influence-degree obtaining process, and a difficulty-degree obtaining process, wherein the influence-degree obtaining process is configured to obtain a backside influence degree representing that a detection of an object to be tracked is affected by other object that overlaps the object, wherein the difficulty-degree obtaining process is configured to calculate, for each object to be tracked, a detection difficulty degree for detecting the object from each of next frames captured by respective cameras, based on the backside influence degree, wherein the tracking process is configured to select the next frame that is included in a set of next frames in a pieces of video and from which the object is to be detected, based on the detection difficulty degree, and detect the object from the selected next frames.