An algorithm combining an improved Auxiliary Particle Filter(APF) with a Markov random field is proposed to achieve multiple target tracking in an infrared scene. First, targets are described according to the gray histogram of target regions.Then, sampling particles of all targets are optimized roughly by using standard APF. Meanwhile, Mean-shift is introduced to the process of auxiliary particle sampling to improve the exponential growth of particle numbers and to increase the percentage of efficient particles and the real-time ability. As for the failure tracking from that targets often are covered each other, a graphic model theory is introduced, in which multi-tracking model by the Markov random field is used to describe the multi-tracking model and convert the problem of multi-target tracking into an inferential problem of the graph model. Results indicate that the new algorithm proposed can track targets only by a few particles, and the accurate rate for multi-target tracking is up to 84%, the failure tracking caused by targets covered mutually can be solved effectively.