NASA's Mars Exploration Rovers (MER) was designed to traverse in Viking Lander-I style terrains: mostly flat, with many small non-obstacle rocks and occasional obstacles. During actual operations in such terrains, onboard position estimates derived solely from the onboard inertial measurement unit and wheel encoder-based odometry achieved well within the design goal of at most 10% error. However, MER vehicles were also driven along slippery slopes tilted as high as 31 degrees. In such conditions an additional capability was employed to maintain a sufficiently accurate onboard position estimate: visual odometry. The MER visual odometry system comprises onboard software for comparing stereo pairs taken by the pointable mast-mounted 45 degree FOV navigation cameras (NAV-CAMs). The system computes an update to the 6-DOF rover pose (x, y, z, roll, pitch, yaw) by tracking the motion of autonomously-selected "interesting" terrain features between two pairs of stereo images, in both 2D pixel and 3D world coordinates. A maximum likelihood estimator is applied to the computed 3D offsets to produce a final, corrected estimate of vehicle motion between the two pairs. In this paper we describe the visual odometry algorithm used on the Mars Exploration Rovers, and summarize its results from the first year of operations on Mars.