Abstract: It is a common issue for Ballistic Missile (BM) to separate warheads in order to improve the penetration probability during reentry phase. For the reasons of unknown warhead number, closeness between target and warheads and similarity of reentry velocities of the warheads which make them moving as a group, how to rapidly associate the separating warheads without any prior information has become an urgent problem. This paper proposes an improved real-time sliding window Markov Chain-Monte Carlo (MCMC) suboptimal association algorithm. By calculating the maximum posterior probability of combination from the surveillance area observations using Monte Carlo method, the algorithm approximates the Markov Chains stable distribution. Furthermore, considering the warhead separation reality, the sliding window MCMC reassigns the weights of the probability association hypothesis and optimizes the inheritance yielding greatly reduction in computation. Simulation results show that the proposed algorithm yields significant improvements both in association and computation performance under heavy dense targets compared with classical Multiple Hypothesis Tracking (MHT).