Regulated choice between cell fate maintenance and differentiation provides decision points in development to progress toward more restricted cell fates or to maintain the current one. Caenorhabditis elegans embryogenesis follows an invariant cell lineage where cell fate is generally more restricted upon each cell division. EMS is a progenitor cell in the four-cell embryo that gives rise to the endomesoderm. We recently found that when ubiquitin-mediated protein degradation is compromised, the anterior daughter of EMS, namely MS, reiterates the EMS fate. This observation demonstrates an essential function of ubiquitin-mediated protein degradation in driving the progression of EMS-to-MS differentiation. Here we report a genome-wide screen of the ubiquitin pathway and extensive lineage analyses. The results suggest a broad role of E3 ligases in driving differentiation progression. First, we identified three substrate-binding proteins for two Cullin–RING ubiquitin ligase (CRL) E3 complexes that promote the progression from the EMS fate to MS, namely LIN-23/β-TrCP and FBXB-3 for the CRL1/SCF complex and ZYG-11/ZYG-11B for the CRL2 complex. Genetic analyses suggest these E3 ligases function through a multifunctional protein OMA-1 and the endomesoderm lineage specifier SKN-1 to drive differentiation. Second, we found that depletion of components of the CRL1/SCF complex induces fate reiteration in all major founder cell lineages. These data suggest that regulated choice between self-renewal and differentiation is widespread during C. elegans embryogenesis as in organisms with regulative development, and ubiquitin-mediated protein degradation drives the choice towards differentiation. Finally, bioinformatic analysis of time series gene expression data showed that expression of E3 genes is transiently enriched during time windows of developmental stage transitions. Transcription factors show similar enrichment, but not other classes of regulatory genes. Based on these findings we propose that ubiquitin-mediated protein degradation, like many transcription factors, function broadly as regulators driving developmental progression during embryogenesis in C. elegans.