A method of tracking an object of an object tracking apparatus is provided. The method includes by performing probability propagation between a set of frames where tracking of a target object is completed and a set of frames where tracking of a target object is not completed among a plurality of frames of an image, calculating a probability map for a target object in each frame included the set of frames where tracking is completed, selecting a frame form the set of frames where tracking is not completed based on the calculated probability map, and determining a location of the target object in the selected frame.