Eukaryotic mRNAs harboring premature translation termination codons are recognized and rapidly degraded by the nonsense-mediated mRNA decay (NMD) pathway. The mechanism for discriminating between mRNAs that terminate translation prematurely and those subject to termination at natural stop codons remains unclear. Studies in multiple organisms indicate that proximity of the termination codon to the 3' poly(A) tail and the poly(A) RNA-binding protein, PAB1, constitute the critical determinant in NMD substrate recognition. We demonstrate that mRNA in yeast lacking a poly(A) tail can be destabilized by introduction of a premature termination codon and, importantly, that this mRNA is a substrate of the NMD machinery. We further show that, in cells lacking Pab1p, mRNA substrate recognition and destabilization by NMD are intact. These results establish that neither the poly(A) tail nor PAB1 is required in yeast for discrimination of nonsense-codon-containing mRNA from normal by NMD.