Directed cell movement involves spatial and temporal regulation of the cortical microtubule (Mt) and actin networks to allow focal adhesions (FAs) to assemble at the cell front and disassemble at the rear. Mts are known to associate with FAs, but the mechanisms coordinating their dynamic interactions remain unknown. Here we show that the CRL3(KLHL21) E3 ubiquitin ligase promotes cell migration by controlling Mt and FA dynamics at the cell cortex. Indeed, KLHL21 localizes to FA structures preferentially at the leading edge, and in complex with Cul3, ubiquitylates EB1 within its microtubule-interacting CH-domain. Cells lacking CRL3(KLHL21) activity or expressing a non-ubiquitylatable EB1 mutant protein are unable to migrate and exhibit strong defects in FA dynamics, lamellipodia formation and cortical plasticity. Our study thus reveals an important mechanism to regulate cortical dynamics during cell migration that involves ubiquitylation of EB1 at focal adhesions.