Robot localization with omnidirectional vision becomes much difficult as the landmark appearances change dramatically in the omnidirectional image. An approach to mobile robot localization with omnidirectional vision was proposed, which used incremental landmark appearance learning to deal with changes of the landmark appearances and to provide observation information for estimating the robot pose under a particle filtering framework. Incremental probabilistic principal analysis was employed to solve the incremental landmark appearance learning problem, where the landmark appearances viewed from different angles were adopted into the learning model. The proposed method can estimate the robot pose accurately since it takes the advantages of particle filtering by means of sequential importance sampling with resampling. The experimental results demonstrate satisfactory performance with low localization error, little computation burden, efficiency, robustness to various interference in omnidirectional vision.