The Yersinia pseudotuberculosis invasin protein promotes bacterial entry by binding to host cell integrins with higher affinity than natural substrates such as fibronectin. The 2.3 angstrom crystal structure of the invasin extracellular region reveals five domains that form a 180 angstrom rod with structural similarities to tandem fibronectin type III domains. The integrin-binding surfaces of invasin and fibronectin include similarly located key residues, but in the context of different folds and surface shapes. The structures of invasin and fibronectin provide an example of convergent evolution, in which invasin presents an optimized surface for integrin binding, in comparison with host substrates.