Nonsense-mediated mRNA decay (NMD) is a translation-dependent RNA degradation pathway involved in many cellular pathways and crucial for telomere maintenance and embryo development. Core NMD factors Upf1, Upf2 and Upf3 are conserved from yeast to mammals, but a universal NMD model is lacking. We used affinity purification coupled with mass spectrometry and an improved data analysis protocol to characterize the composition and dynamics of yeast NMD complexes in yeast (112 experiments). Unexpectedly, we identified two distinct complexes associated with Upf1: Upf1-23 (Upf1, Upf2, Upf3) and Upf1-decappingUpf1-decapping contained the mRNA decapping enzyme, together with Nmd4 and Ebs1, two proteins that globally affected NMD and were critical for RNA degradation mediated by the Upf1 C-terminal helicase region. The fact that Nmd4 association with RNA was partially dependent on Upf1-23 components and the similarity between Nmd4/Ebs1 and mammalian Smg5-7 proteins suggest that NMD operates through conserved, successive Upf1-23 and Upf1-decapping complexes. This model can be extended to accommodate steps that are missing in yeast, to serve for further mechanistic studies of NMD in eukaryotes.