Future Mars Rotorcraft require advanced navigation capabilities to enable all terrain access over long distance flights that are executed fully autonomously. A critical component to enable precision navigation during long traverses is the ability to perform on-board absolute localization to eliminate drift in position estimates of the on-board odometry algorithm. In this paper, we present an approach for on-board map-based localization to provide global reference position based on orbital or aerial image maps. Our approach builds on a vision-based localization method to localize against a map derived from HiRISE image products - an ortho-projected image (ortho-image) and a corresponding digital elevation map. The map is pre-computed using a feature-based approach. Features are stored with their 3D world coordinates, and a descriptor to code the local image intensity information in the vicinity of the feature location. An on-board matching algorithm uses this information to match visual features in a query image acquired during flight, guided by a pose prior from the on-board range-visual-inertial state estimator (Range-VIO). Valid matches are then used by a perspective-n-point (PnP) algorithm to estimate the absolute pose of the vehicle in a global frame. We demonstrate and evaluate our approach on simulated data, and data from UAS flights.