Many pathogens are equipped with factors providing resistance against the bactericidal action of complement. Yersinia enterocolitica, a Gram-negative enteric pathogen with invasive properties, efficiently resists the deleterious action of human complement. The major Y. enterocolitica serum resistance determinants include outer membrane proteins YadA and Ail. Lipopolysaccharide (LPS) O-antigen (O-ag) and outer core (OC) do not contribute directly to complement resistance. The aim of this study was to analyze a possible mechanism whereby Y. enterocolitica could inhibit the antibody-mediated classical pathway of complement activation. We show that Y. enterocolitica serotypes O:3, O:8, and O:9 bind C4b-binding protein (C4bp), an inhibitor of both the classical and lectin pathways of complement. To identify the C4bp receptors on Y. enterocolitica serotype O:3 surface, a set of mutants expressing YadA, Ail, O-ag, and OC in different combinations was tested for the ability to bind C4bp. The studies showed that both YadA and Ail acted as C4bp receptors. Ail-mediated C4bp binding, however, was blocked by the O-ag and OC, and could be observed only with mutants lacking these LPS structures. C4bp bound to Y. enterocolitica was functionally active and participated in the factor I-mediated degradation of C4b. These findings show that Y. enterocolitica uses two proteins, YadA and Ail, to bind C4bp. Binding of C4bp could help Y. enterocolitica to evade complement-mediated clearance in the human host.