In UAV visual localization applications, the quality of image matching directly affects both the precision and reliability of the visual localization task. In UAV visual localization tasks, high-resolution remote sensing images are typically used as reference maps, whereas UAV-acquired aerial images serve as real-time inputs, enabling the estimation of the UAV’s spatial position through image matching. However, due to the substantial difference in imaging mechanisms and acquisition conditions between reference and real-time images, heterogeneous image pairs often contain numerous outliers, which significantly hinder the direct application of traditional matching algorithms such as RANSAC. To address these challenges, a spatial consistency-guided sampling algorithm is proposed. First, the initial correspondences are constructed based on triplet relationships, and their structural features are subsequently extracted. Then, a minimal subset sampling strategy is developed to improve sampling efficiency. Next, a data subset refinement strategy is introduced to further improve the robustness of sampling. Finally, extensive comparative experiments are conducted on the University-1652 and DenseUAV public datasets against several state-of-the-art feature matching algorithms. The experimental results demonstrate that the proposed algorithm achieves superior performance in correct matching rate, substantially enhancing the matching performance in heterogeneous image matching. Moreover, the proposed algorithm requires approximately 0.15 s per matching on average, and while maintaining the highest matching accuracy, it exhibits significantly higher computational efficiency than advanced sampling algorithms such as TRESAC and RANSAC, demonstrating strong potential for real-time applications in UAV visual localization tasks.