Image-based target tracking methods rely on continuous image acquisition and post-processing, which will result in low tracking efficiency. To realize real-time tracking of fast moving objects, we propose an image-free target tracking scheme based on the discrete cosine transform and single-pixel detection. Our method avoids calculating all the phase values, so the number of samples can be greatly reduced. Furthermore, complementary modulation is applied to reduce the measurement noise, and background subtraction is applied to enhance the contrast. The results of simulations and experiments demonstrate that the proposed scheme can accomplish the tracking task in a complex background with a sampling ratio of less than 0.59% of the Nyquist-Shannon criterion, thereby significantly reducing the measurement time. The tracking speed can reach 208 fps at a spatial resolution of 128 × 128 pixels with a tracking error of no more than one pixel. This technique provides a new idea for real-time tracking of fast-moving targets.