This paper proposes an efficient Adaptive Large Neighborhood Search (ALNS) algorithm for the Flying Sidekick Traveling Salesman Problem (FSTSP). The algorithm integrates a stage-based truck–drone solution representation, two complementary destroy–repair operator groups, and six local-search neighborhoods focusing on drone operations and truck–drone interactions. Computational efficiency is enhanced through constant-time move evaluation after preprocessing and Static Move Descriptors, while an adaptive penalty mechanism handles drone endurance constraints. Extensive experiments on 336 benchmark instances demonstrate strong performance across problem sizes. On small instances, ALNS recovers all 72 known MC-set optimal benchmark values across 720 independent runs, averaging only 0.76 seconds per run. On 90 Agatz-S instances, it matches or improves the dynamic-programming reference solutions in 83.9\% of runs, with an average gap of just 0.02\%. On 150 medium-to-large Agatz-L instances (50–250 customers), ALNS achieves average mean-objective improvements of 1.28\%, 3.77\%, and 3.01\% over MD–SPP–H, EP–All, and SPP–All, respectively, with statistically significant differences. On 60 Ha-set instances, it further improves mean solution quality by 1.51\% over MD–SPP–H and 3.14\% over HGA–TAC. For 100-customer Ha-set instances, ALNS also reduces runtime by 47.2\% and 44.5\% relative to these methods, respectively. Ablation and robustness analyses further confirm the effectiveness and reliability of the proposed framework.