Legged robots offer the potential to navigate highly challenging terrain, and there has recently been much progress in this area. However, a great deal of this recent work has operated under the assumption that either the robot has complete knowledge of its environment or that its environment is suitably regular so as to be navigated with only minimal perception, an unrealistic assumption in many real-world domains. In this paper we present an integrated perception and control system for a quadruped robot that allows it to perceive and traverse previously unseen, rugged terrain that includes large, irregular obstacles. A key element of the system is a novel terrain modeling algorithm, used for filling in the occluded models resulting from on-board vision systems. We apply our approach to the LittleDog robot, and show that it allows the robot to walk over challenging terrain using only on-board perception.