Visual localization of Unmanned Aerial Vehicles (UAVs) using satellite imagery enables GNSS-freenavigation but faces a fundamental challenge: the extreme domain gap between aerial and satelliteviews causes visual place recognition (VPR) to fail unpredictably along the trajectory. We identifythat a primary cause of this failure is heading-dependent feature ambiguity—standard CNN featuresare not rotation invariant, causing matches to degrade when the UAV’s heading deviates from thesatellite’s canonical North orientation. We present NaviLoc, a three-stage localization pipeline thataddresses this through heading rectification: after coarse global alignment, we rotate query images toa canonical orientation using VIO-derived headings before extracting features for local refinement.Combined with overlapping sliding-window SE(2) optimization, NaviLoc achieves 20.38m AbsoluteTrajectory Error (ATE) on a challenging UAV-to-satellite benchmark—a 31× improvement over VIOdrift and 17× over state-of-the-art VPR methods. Our approach requires no dataset-specific tuningand runs in real-time using a lightweight MobileNet-V3 backbone.