Vision-based mobile robot navigation requires robust methods for planning and executing tasks due to the unreliability of visual information. We propose a new method for reliable vision-based navigation in an unmodeled dynamic environment. Artificial landmarks are used as visual cues for navigation. Our system builds a visiblity graph among landmark locations during an exploration phase and then uses that graph for navigation . To deal with temporary occlusion of landmarks, long-term changes in the environment, and inherent uncertainties in the landmark detection process, we use a probabilistic model of landmark visibility. Based on the history of previous observations made, each visibility edge in the graph is annotated with an estimated probability of landmark visibility. Based on the history of previous observations made, each visibility edge in the graph is annotated with an estimated probability of landmark detection. To solve a navigation task, our algorithm computes the expected shortest paths between all landmarks and the specified goal, by solving a special instance of a Markov decision process.