In this paper, we propose a robust state-based structured support vector machine (SVM) tracking algorithm combined with incremental principal component analysis (PCA). Different from the current structured SVM for tracking, our method directly learns and predicts the object's states and not the 2-D translation transformation during tracking. We define the object's virtual state to combine the state-based structured SVM and incremental PCA. The virtual state is considered as the most confident state of the object in every frame. The incremental PCA is used to update the virtual feature vector corresponding to the virtual state and the principal subspace of the object's feature vectors. In order to improve the accuracy of the prediction, all the feature vectors are projected onto the principal subspace in the learning and prediction process of the state-based structured SVM. Experimental results on several challenging video sequences validate the effectiveness and robustness of our approach.