A processor-implemented method with object tracking includes: determining an initial template image based on an input bounding box and an input image; generating an initial feature map by extracting features from the initial template image; generating a transformed feature map by performing feature transformation adapted to objectness on the initial feature map; generating an objectness probability map and a bounding box map indicating bounding box information corresponding to each coordinate of the objectness probability map by performing objectness-based bounding box regression analysis on the transformed feature map; and determining a refined bounding box based on the objectness probability map and the bounding box map.