In this paper we present a new probabilistic feature-based approach to multi-hypothesis global localization and pose tracking. Hypotheses are generated using a constraintbased search in the interpretation tree of possible localto-global pairings. This results in a set of robot location hypotheses of unbounded accuracy. For tracking, the same constraint-based technique is used. It performs track splitting as soon as location ambiguities arise from uncertainties and sensing. This yields a very robust localization technique which can deal with significant errors from odometry, collisions and kidnapping. Simulation experiments and first tests with a real robot demonstrate these properties at very low computational cost. The presented approach is theoretically sound which makes that the only parameter is the significance level on which all statistical decisions are taken.