Advances in wireless communication and microelectronic devices technologies have enabled the development of low-power micro-sensors and the deployment of large scale sensor networks. With the capabilities of pervasive surveillance, sensor networks can be very useful in a lot of commercial and military applications for collecting and processing the environmental data. One of the very interesting research issues is the energy saving in object tracking sensor networks (OTSNs). However, most of the past studies focused only on the aspect of movement behavior analysis or location tracking and did not consider the temporal characteristics, which are very critical in OTSNs. In this paper, we propose a novel data mining method named TMP-Mine with a special data structure named TMP-Tree for discovering temporal moving patterns efficiently. To our best knowledge, this is the first study that explores the issue of discovering temporal moving patterns that contain both movement and time interval simultaneously. Through empirical evaluation on various simulation conditions, TMP-Mine is shown to deliver excellent performance in terms of accuracy, execution efficiency, and scalability.