We proposed a new method for outdoor route-following using a sky-view sequence. The sky-view is taken through an upward fisheye lens, and provides a clear field-of-view which is undisturbed by environmental changes and occlusions on the ground. We developed an image-matching method that estimates the robot’s position (location and orientation) robustly to the sky condition, the harsh sunshine and the seasonal changes of trees. The integration of the image matching and a dead-reckoning technique made continuous position estimation in the real world possible. We verified the basic performance of the system in a crowded campus, and demonstrated the accurate navigation which is equal to or superior to GPS-based navigation.