Heavy reliance on GPS is preventing unmanned air systems (UAS) from being fully inte- grated for many of their numerous applications. In the absence of GPS, GPS-reliant UAS have difficulty estimating vehicle states resulting in vehicle failures. Additionally, naively using erro- neous measurements when GPS is available can result in significant state inaccuracies. We present a simultaneous localization and mapping (SLAM) solution to GPS-degraded navigation that al- lows vehicle state estimation and control independent of global information. Optionally, a global map can be constructed from odometry measurements and can be updated with GPS measurements while maintaining robustness against outliers.We detail a relative navigation SLAM framework that distinguishes a relative front end and global back end. It decouples the front-end flight critical processes, such as state estimation and control, from back-end global map construction and optimization. Components of the front end function relative to a locally-established coordinate frame, completely independent from global state information. The approach maintains state estimation continuity in the absence of GPS mea- surements or when there are jumps in the global state, such as after map optimization. A global graph-based SLAM back end complements the relative front end by constructing and refining a global map using odometry measurements provided by the front end.Unlike typical approaches that use GPS in the front end to estimate global states, our unique back end uses a virtual zero and virtual constraint to allow intermittent GPS measurements to be applied directly to the map. Methods are presented to reduce the scale of GPS induced costs and refine the map’s initial orientation prior to optimization, both of which facilitate convergence to a globally consistent map. The approach uses a state-of-the-art robust least-squares optimization algorithm called dynamic covariance scaling (DCS) to identify and reject outlying GPS measure- ments and loop closures. We demonstrate our system’s ability to generate globally consistent and aligned maps in GPS-degraded environments through simulation, hand-carried, and flight test re- sults.