We propose an efficient and robust tracking method based on minimum barrier distance (MBD) and spatio-temporal context (STC) learning. It is robust to noise and blur, and can be evaluated approximately through a Dijkstra-like algorithm, leading to fast computation. We adopt the MBD transform to measure the weights of context pixels, and formulate the spatio-temporal relationship between the object and its surrounding region based on a Bayesian framework to estimate the most likely location of the target. A bounded scale update model is proposed to estimate the size of the object. The whole proposed method runs at nearly 160 frames per second (FPS) on an i5 machine. Extensive experimental results show it has comparable or better comprehensive performance than the original STC and some other leading methods.