Video object tracking represents a very important computer vision domain. In this paper, a perceptual hashing based template-matching method for object tracking is proposed to efficiently track objects in challenging video sequences. In the tracking process, we first apply three existing basic perceptual hashing techniques to visual tracking, namely average hash (aHash), perceptive hash (pHash) and difference hash (dHash). Compared with previous tracking methods such as mean-shift or compressive tracking (CT), perceptual hashing-based tracking outperforms in terms of efficiency and accuracy. In order to further improve the accuracy of object localization and the robustness of tracking, we propose Laplace-based Hash (LHash) and Laplace-based Difference Hash (LDHash). By qualitative and quantitative comparison with some representative tracking algorithms, experimental results show that our improved perceptual hashing-based tracking algorithms perform favorably against the state-of-the-art algorithms under various challenging environments in terms of time cost, accuracy and robustness. Since our improved perceptual hashing can be a compact and efficient representation of objects, it can be further applied to fusing with depth information for more robust RGB-D video tracking.