Multiple-target tracking in video (MTTV) presents a technical challenge in video surveillance applications. In this paper, we formulate the MTTV problem using dynamic Markov network (DMN) techniques. Our model consists of three coupled Markov random fields: 1) a field for the joint state of the multitarget; 2) a binary random process for the existence of each individual target; and 3) a binary random process for the occlusion of each dual adjacent target. To make the inference tractable, we introduce two robust functions that eliminate the two binary processes. We then propose a novel belief propagation (BP) algorithm called particle-based BP and embed it into a Markov chain Monte Carlo approach to obtain the maximum a posteriori estimation in the DMN. With a stratified sampler, we incorporate the information obtained from a learned bottom-up detector (e.g., support-vector-machine-based classifier) and the motion model of the target into the message propagation. Other low-level visual cues such as motion and shape can be easily incorporated into our framework to obtain better tracking results. We have performed extensive experimental verification, and the results suggest that our method is comparable to the state-of-art multitarget tracking methods in all the cases we tested.