The control of mRNA stability plays a central role in regulating gene expression. In metazoans, the earliest stages of development are driven by maternally supplied mRNAs. The degradation of these maternal mRNAs is critical for promoting the maternal-to-zygotic transition of developmental programs, although the underlying mechanisms are poorly understood in vertebrates. Here, we characterized maternal mRNA degradation pathways in zebrafish using a transcriptome analysis and systematic reporter assays. Our data demonstrate that ORFs enriched with uncommon codons promote deadenylation by the CCR4-NOT complex in a translation-dependent manner. This codon-mediated mRNA decay is conditional on the context of the 3′ UTR, with long 3′ UTRs conferring resistance to deadenylation. These results indicate that the combined effect of codon usage and 3′ UTR length determines the stability of maternal mRNAs in zebrafish embryos. Our study thus highlights the codon-mediated mRNA decay as a conserved regulatory mechanism in eukaryotes.