Visual tracking is one of the most popular research topics in the domain of computer vision. It is a challenging task to develop an effective and efficient tracking algorithm because of template drift problems. To alleviate the drift, the multiple instance learning (MIL) method has been applied to target tracking. However, there must be a sufficient amount of useful data for online MIL to learn at the outset, which actually increases the computational complexity. In this paper, an effective tracking algorithm is proposed which uses an online MIL based on the compressed appearance model to accomplish object tracking. In order to decrease the computational complexity and obtain sufficient data for online learning adaptive appearance model, Features are extracted by non-adaptive random projections of the multi-scale image feature space based on compressive sensing theories. The experimental results on various videos show that the proposed method has a satisfactory performance in real-time object tracking.