In this paper, we propose a novel approach for integrating multiple tracking cues within a unified probabilistic graph-based Markov random fields (MRFs) representation. We show how to integrate temporal and spatial cues encoded by unary and pairwise probabilistic potentials. As the inference of such high-order MRF models is known to be NP-hard, we propose an efficient spectral relaxation-based inference scheme. The proposed scheme is exemplified by applying it to a mixture of five tracking cues, and is shown to be applicable to wider sets of cues. This paves the way for a modular plug-and-play tracking framework that can be easily adapted to diverse tracking scenarios. The proposed scheme is experimentally shown to compare favorably with contemporary state-of-the-art schemes, and provides accurate tracking results.