In this paper, we describe our work on a robot navigation system using an omnidirectional camera as the primary sensor. An omnidirectional structure from motion algorithm is presented with its uncertainty analyzed. We evaluate the omnidirectional SFM on both synthetic data and on real image sequences. Comparison with the conventional camera is made and we show that in certain situations the omnidirectional SFM gives better results than the conventional one by taking advantage of its larger field of view.