Protein O-fucosyltransferase 1 (POFUT1) fucosylates the epidermal growth factor (EGF)-like domains found in cell-surface and secreted glycoproteins including Notch and its ligands. Although Notch fucosylation is critical for development, and POFUT1 deficiency leads to human disease, how this enzyme binds and catalyzes the fucosylation of its diverse EGF-like domain substrates has not been determined. Reported here is the X-ray crystal structure of mouse POFUT1 in complex with several EGF-like domains, including EGF12 and EGF26 of Notch. Overall shape complementarity, interactions with invariant atoms of the fucosylation motif and flexible segments on POFUT1 all define its EGF-like-domain binding properties. Using large-scale structural and sequence analysis, we also show that POFUT1 binds EGF-like domains of the hEGF type and that the highly correlated presence of POFUT1 and fucosylatable hEGFs has accompanied animal evolution.