Mobile robot localization deals with uncertain sensory information as well as uncertain data association. In this paper we present a probabilistic feature-based approach to global localization and pose tracking which explicitly addresses both problems. Location hypotheses are represented as Gaussian distributions. Hypotheses are found by a search in the tree of possible local-to-global feature associations, given a local map of observed features and a global map of the environment. During tree traversal, several types of geometric constraints are used to determine statistically feasible associations. As soon as hypotheses are available, they are tracked using the same constraint-based technique. Track splitting is performed when location ambiguity arises from uncertainties and sensing. This yields a very robust localization technique which can deal with significant errors from odometry, collisions and kidnapping. Experiments in simulation and with a real robot demonstrate these properties at low computational costs.