All is a 17-kDa chromosomally encoded outer membrane protein that mediates serum resistance (complement resistance) in the pathogenic Yersiniae (Yersinia pestis, Y. enterocolitica, and Y. pseudotuberculosis). In this article, we demonstrate that Y pseudotuberculosis Ail from strains PB1, 2812/79, and YPIII/pIB1 (serotypes O:1a, O:1b, and O:3, respectively) can bind the inhibitor of the classical and lectin pathways of complement, C4b-binding protein (C4BP). Binding was observed irrespective of serotype tested and independently of YadA, which is the primary C4BP receptor of Y. enterocolitica. Disruption of the a gene in Y. pseudotuberculosis resulted in loss of C4BP binding. Cofactor assays revealed that bound C4BP is functional, because bound C4BP in the presence of factor I cleaved C4b. In the absence of YadA, Ail conferred serum resistance to strains PB1 and YPIII, whereas serum resistance was observed in strain 2812/79 in the absence of both YadA and Ail, suggesting additional serum resistance factors. Ail from strain YPIII/pIB1 alone can mediate serum resistance and C4BP binding, because its expression in a serum-sensitive laboratory strain of Escherichia coli conferred both of these phenotypes. Using a panel of C4BP mutants, each deficient in a single complement control protein domain, we observed that complement control protein domains 6-8 are important for binding to Ail. Binding of C4BP was unaffected by increasing heparin or salt concentrations, suggesting primarily nonionic interactions. These results indicate that Y. pseudotuberculosis Ail recruits C4BP in a functional manner, facilitating resistance to attack from complement. The Journal of Immunology, 2012, 188: 4450-4459.