A processor-implemented method with target object tracking includes: setting a search area for a target object included in an input image based on a position of a first target box in a template image; selecting a network path from a plurality of network paths of a neural network model according to a resizing ratio of a size of another image that is input to the neural network model to a size of the search area; and tracking the target object by estimating a position of a second target box corresponding to the target object in the input image according to the selected network path.