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. We propose a two-step online multi-object tracking framework that incorporates a confidence-aided relative motion network (RMN) to jointly consider various difficulties. Because of the framework’s two-step data association process and the similarity function using RMNs, the proposed method achieves robust performance in the presence of most kinds of uncertainties. In our experiments, the proposed method exhibits a very robust and efficient performance compared with other state-of-the-art algorithms.