Rather than the difficulties of highly non-linear and non-Gaussian observation process and the state distribution in single target tracking, the presence of a large, varying number of targets and their interactions place more challenge on visual tracking. To overcome these difficulties, we formulate multiple targets tracking problem in a dynamic Markov network which consists of three coupled Markov random fields that model the following: a field for joint state of multi-target, one binary process for existence of individual target, and another binary process for occlusion of dual adjacent targets. By introducing two robust functions, we eliminate the two binary processes, and then apply a novel version of belief propagation called sequential stratified sampling belief propagation algorithm to obtain the maximum a posteriori (MAP) estimation in the dynamic Markov network. By using stratified sampler, we incorporate bottom-up information provided by a learned detector (e.g. SVM classifier) and belief information for the messages updating. Other low-level visual cues (e.g. color and shape) can be easily incorporated in our multi-target tracking model to obtain better tracking results. Experimental results suggest that our method is comparable to the state-of-the-art multiple targets tracking methods in several test cases.