The ability to localize an unmanned vehicle is an essential requirement for extraterrestrial robotic exploration missions. The goal of this thesis is to develop a visual odometry algorithm capable of operating in real-time and in natural unstructured environments. Accuracy, repeatability and computational cost were the primary considerations during the development of the algorithm. The resulting visual odometry algorithm can operate in real-time and provides the foundations for further development. More commonly used approaches for localization include the use of inertial measurement units (IMU) or wheel odometry, which are prone to drift and slippage respectively, making them unreliable for long duration missions. Visual odometry also experiences error accumulation, however, it offers the possibility of mitigating this problem through techniques such as loop closing and bundle adjustment. The performance of the Iterative Closest Point (ICP) algorithm in conjunction within the visual odometer was also evaluated and shown to have improved overall localization performance.