Traditional sparse representation algorithms attempt to build a robust appearance model to track targets according to the linear combination of sparse dictionaries. However, such algorithms ignore the hierarchical structure features of the tracking object; thus, handling complex tracking scenery is difficult. In this paper, an innovative convolution-based sparse tracking algorithm (CSTA) is proposed to address this limitation. Local image patches extracted within the object region serve as local descriptors. According to the sparse representation theory, a group of sparse image blocks is selected as the fixed convolution kernel, and the results obtained by convoluting the convolution kernel with the input image demonstrate that the hierarchical structure of tracking objects has been preserved. In addition, a selective online updating mechanism is presented to avoid the drift problem caused by erroneous model updating. Quantitative and qualitative analyses are conducted, and the proposed CSTA and advanced sparse representation algorithms are compared using open datasets. The experimental results demonstrate that the proposed CSTA outperforms state-of-the-art sparse tracking algorithms in terms of accuracy and robustness.