Sister-chromatid cohesion is established during S phase when Eco1 acetylates cohesin. In budding yeast, Eco1 activity falls after S phase due to Cdk1-dependent phosphorylation, which triggers ubiquitination by SCF(Cdc4). We show here that Eco1 degradation requires the sequential actions of Cdk1 and two additional kinases, Cdc7-Dbf4 and the GSK-3 homolog Mck1. These kinases recognize motifs primed by previous phosphorylation, resulting in an ordered sequence of three phosphorylation events on Eco1. Only the latter two phosphorylation sites are spaced correctly to bind Cdc4, resulting in strict discrimination between phosphates added by Cdk1 and by Cdc7. Inhibition of Cdc7 by the DNA damage response prevents Eco1 destruction, allowing establishment of cohesion after S phase. This elaborate regulatory system, involving three independent kinases and stringent substrate selection by a ubiquitin ligase, enables robust control of cohesion establishment during normal growth and after stress.