Nonsense-mediated mRNA decay (NMD) is a critical post-transcriptional surveillance mechanism that degrades transcripts with premature termination codons, safeguarding transcriptome integrity and shaping disease phenotypes. However, accurately predicting NMD efficiency remains challenging, as existing models often rely on simplistic rule-based heuristics or limited feature sets, constraining their accuracy and generalizability. Using paired DNA and RNA data from The Cancer Genome Atlas, we benchmark embedding-only models and demonstrate that they underperform compared to a simple rule-based approach. To address this, we develop NMDEP (NMD Efficiency Predictor), an integrative framework that combines optimized rule-based methods, sequence embeddings, and curated biological features, achieving state-of-the-art predictive performance. Through explainable AI, we identify key NMD determinants, reaffirming established factors such as variant position while uncovering novel contributors like ribosome loading. Applied to over 2.9 million simulated stop-gain variants, NMDEP facilitates large-scale mRNA degradation assessments, advancing variant interpretation and disease research.