Modern navigation systems rely critically on GNSS, which in many cases is unavailable or unreliable (e.g. due to jamming or spoofing). For this reason there is great interest in augmenting backup navigation systems such as inertial navigation systems (INS) with additional modalities that reduce positioning error in the absence of reliable GNSS. Magnetic-anomaly navigation is one such approach, providing passive, non-jammable navigation through periodic position fixes obtained by comparing local measurements of Earth's crustal field against known anomaly maps. Despite its potential, existing MagNav efforts have been limited by magnetometer performance and platform noise; solutions addressing these problems have proven either too brittle or impractical for realistic deployment. Here we demonstrate a quantum-assured MagNav solution based on proprietary quantum magnetometers with by a novel denoising and map-matching algorithms. The system fits on fixed-wing drones or in the avionics bay of a commercial airliner. We present trials at altitudes up to 19000 feet, testing onboard and outboard quantum magnetometers comparing against a strategic-grade INS. Our MagNav solution achieves superior performance, delivering up to 46x better positioning error than the velocity-aided INS; the best final positioning accuracy we achieve is 22m or 0.006% of the flight distance. Airborne trials consistently achieve at least 11x advantage over the INS across varying conditions, altitudes, and flight patterns. The system learns model parameters online without special vehicle maneuvers providing robustness to various configuration changes (e.g. changing payload or latitude). Our trials also include the first successful MagNav performed in a ground vehicle using publicly-available anomaly maps, delivering bounded positioning error 7x lower than the INS, with both systems in strapdown configuration.