Successive images of a scene are captured and then further processed to achieve the moving object tracking. However, due to modulation rate limitations of the spatial light modulator in single-pixel imaging (SPI) system, the imaging frame rate cannot meet the high-resolution and real-time requirements for object tracking. In this paper, we demonstrate a fast object tracking technique based on SPI with an ultra-low sampling rate that is independent of imaging. We construct modulation information that satisfies the projection conditions and can transform 2D images into 1D projection curves. The 1D projection curves, which provide the location information of the moving object, can be obtained with high resolution in real-time, and then the tracking of the moving object is realized. A background subtraction technique for tracking moving objects that removes static components from a scene is also proposed. The proposed technique is verified by computational simulations and laboratory experiments. In the laboratory experiments, we demonstrate that the proposed method can be used to track moving objects with less than 0.2% of the measurements established by the Nyquist criterion, and it presents a resolution of 256×256 pixels at ~177 fps. The reported technique accelerates the tracking speed of SPI and provides an efficient strategy for remote sensing and biomedical applications.