In many visual multi-object tracking applications, the question when to add or remove a target is not trivial due to, for example, erroneous outputs of object detectors or observation models that cannot describe the full variability of the objects to track. In this paper, we present a real-time, online multi-face tracking algorithm that effectively deals with missing or uncertain detections in a principled way. To this end, we propose to use long-term image observations, and an explicit probabilistic filtering framework that decides when to add or remove a target from the tracker. We evaluated the proposed method on three different difficult datasets with a total length of more than 9 hours and show a significant increase in performance of the tracking.