Robotics research in recent years has experienced a significant growth in using vision by mobile robots to map an environment and negotiate routes within the environment. This growth is attributed to the rich textural information in visual sensory data compared with the traditional range data, and it is fueled by efficient and accurate algorithms that have been developed in computer vision and robotics community. In spite of the impressive progress, current visual robot localization and navigation algorithms still face challenges among which are their scalability in handling large environments and their robustness with respect to dynamic changes of the environments. In this talk, I will overview the existing efforts including our attempts at addressing the above two challenges. In particular, I will present compact whole-image encoding as a promising avenue for achieving scalable visual robot localization, and introduce the use of optical flow statistics in dealing with changes in environment illumination. I will show experiments that demonstrate the effectiveness of our robot localization and navigation algorithms.