An essential aspect of innate immunity is recognition of molecular patterns on the surface of pathogens or altered self through the lectin and classical pathways, two of the three well-established activation pathways of the complement system. This recognition causes activation of the MASP-2 or the C1s serine proteases followed by cleavage of the protein C4. Here we present the crystal structures of the 203-kDa human C4 and the 245-kDa C4·MASP-2 substrate·enzyme complex. When C4 binds to MASP-2, substantial conformational changes in C4 are induced, and its scissile bond region becomes ordered and inserted into the protease catalytic site in a manner canonical to serine proteases. In MASP-2, an exosite located within the CCP domains recognizes the C4 C345C domain 60 Å from the scissile bond. Mutations in C4 and MASP-2 residues at the C345C-CCP interface inhibit the intermolecular interaction and C4 cleavage. The possible assembly of the huge in vivo enzyme-substrate complex consisting of glycan-bound mannan-binding lectin, MASP-2, and C4 is discussed. Our own and prior functional data suggest that C1s in the classical pathway of complement activated by, e.g., antigen-antibody complexes, also recognizes the C4 C345C domain through a CCP exosite. Our results provide a unified structural framework for understanding the early and essential step of C4 cleavage in the elimination of pathogens and altered self through two major pathways of complement activation.