Applications for tracking multiple objects in an image sequence are frequently challenged by various uncertainties such as occlusion, misdetection, and abrupt camera motion. In practical environments, these uncertainties may occur simultaneously and with no pattern, so that they must be jointly considered to achieve reliable tracking. In this paper, we propose a two-step online multi-object tracking framework that incorporates a confidence-aided relative motion network to jointly consider various difficulties. Because of the framework’s two-step data association process and the similarity function using relative motion networks, the proposed method achieves robust performance in the presence of most kinds of uncertainties. In our experiments, the proposed method exhibits very robust and efficient performance compared with other state-of-the-art algorithms.