Mars airplane is one of the candidate payloads of JAXA's next Mars exploration program. Airborne observation of Mars is expected to fill the “gap” between rovers, which provides a detailed observation but a limited area of coverage, and orbiters, which can cover a wide range of area but with a limited resolution. Two key challenges to realize a Mars airplane are 1) unavailability of GPS for localization and 2) limited computing power due to tight restriction on the mass of on-board instrument. We address these issues by developing a computationally tractable vision-based navigation algorithm. Our approach is based on an efficient feature detector and descriptor, Oriented FAST and Rotated BRIEF (ORB), combined with the information from an inertial measurement unit (IMU) using the extended Kalman filter (EKF) method. In this paper, we demonstrate the proposed ORB/EKF-based localization method by indoor experiments, using a small quadrotor helicopter and Mars surface image from Mars Reconnaissance Orbiter. The experimental results indicate that the computational cost of the proposed method is sufficiently small for real-time processing.