The tracking of infrared small target may be unstable due to the interference of background clutter and imaging noise. Moreover, the changing target appearance could degrade the tracking robustness. How to estimate the target spatial-temporal structure is the key to enhance the tracking stability for appearance changing small target under heavy clutter. This paper proposes a robust target tracking algorithm based on sparse representation and Bayesian inference that can estimate and predict the target spatial-temporal structure. Firstly, the small target signal is sparsely decomposed on the generalized Gaussian target over-complete dictionary (GGTOD). In this way the spatial structure information of small target is extracted from the noised and clutter contaminated infrared image. Then, according to the long term observations the long term temporal-spatial structure distribution of the target is established. Meanwhile the short term target temporal-spatial structure distribution is built according to the short term observations. Finally, the long term structure distribution and the short term structure distribution are combined by Bayesian inference to estimate and predict the target temporal-spatial structure in the next frame. By estimating the temporal change of target spatial structure, the proposed method achieves outstanding adaptability to the changing small target and robustness to clutter disturbance. Experiments on various infrared sequences show that the proposed method not only can estimate and predict the temporal-spatial structure of small target accurately but also can track the appearance changing small target stably under the inference of heavy clutter and noise. © 2019 Elsevier B.V.