In this paper we present a vision-based approach to mobile robot localization, that integrates an image retrieval system with Monte-Carlo localization. The image retrieval process is based on features that are invariant with respect to image translations, rotations, and limited scale. Since it furthermore uses local features, the system is robust against distortion and occlusions which is especially important in populated environments. The sample-based Monte-Carlo localization technique allows our robot to efficiently integrate multiple measurements over time. Both techniques are combined by extracting for each image a set of possible view-points using a two-dimensional map of the environment. Our technique has been implemented and tested extensively using data obtained with a real robot. We present several experiments demonstrating the reliability and robustness of our approach.