Post-transcriptional regulation is crucial to shape gene expression. During the Maternal-to-Zygotic Transition (MZT), thousands of maternal transcripts are regulated upon fertilization and genome activation. Transcript stability can be influenced by cis-elements and trans-factors, but how these inputs are integrated to determine the overall mRNA stability is unclear. Here, we show that most transcripts are under combinatorial regulation by multiple decay pathways during zebrafish MZT. To identify cis-regulatory elements, we performed a massively parallel reporter assay for stability-influencing sequences, which revealed that 3'-UTR poly-U motifs are associated with mRNA stability. In contrast, miR-430 target sequences, UAUUUAUU AU-rich elements (ARE), CCUC and CUGC elements emerged as the main destabilizing motifs in the embryo, with miR-430 and AREs causing mRNA deadenylation in a genome activation-dependent manner. To identify the trans-factors interacting with these cis-elements, we comprehensively profiled RNA-protein interactions and their associated regulatory activities across the transcriptome during the MZT. We find that poly-U binding proteins are preferentially associated with 3'-UTR sequences and stabilizing motifs, and that antagonistic sequence contexts for poly-C and poly-U binding proteins shape the binding landscape and magnitude of regulation across the transcriptome. Finally, we integrate these regulatory motifs into a machine learning model that accurately predicts the stability of mRNA reporters in vivo. Our findings reveal how mechanisms of post-transcriptional regulation are coordinated to direct changes in mRNA stability within the early zebrafish embryo.