This paper presents a robust object tracking method using a sparse shape-based object model. Our approach consists of three ingredients namely shapes, a motion model and a sparse (non-binary) subsampling of colours in background and foreground parts based on the shape assumption. The tracking itself is inspired by the idea of having a short-term and a long-term memory. A lost object is ”missed” by the long-term memory when it is no longer recognized by the short-term memory. Moreover, the long-term memory allows to re-detect vanished objects and using their new position as a new initial position for object tracking. The short-term memory is implemented with a new Monte Carlo variant which provides a heuristic to cope with the loss-of-diversity problem. It enables simultaneous tracking of multiple (visually) identical objects. The long-term memory is implemented with a Bayesian Multiple Hypothesis filter. We demonstrate the robustness of our approach with respect to object occlusions and non-Gaussian/non-linear movements of the tracked object. We also show that tracking can be significantly improved by using compensating ego-motion. Our approach is very scalable since one can tune the parameters for a trade-off between precision and computational time.