Surface display technologies have been established previously to select peptides and polypeptides that interact with purified immobilized ligands. In the present study, we designed and implemented a surface display-based technique to identify novel peptide motifs that mediate entry into eukaryotic cells. An Escherichia coli library expressing surface-displayed peptides was combined with eukaryotic cells and the gentamicin protection assay was performed to select recombinant E. coli, which were internalized into eukaryotic cells by virtue of the displayed peptides. To establish the proof of principle of this approach, the fibronectin-binding motifs of the fibronectin-binding protein A of Staphylococcus aureus were inserted into the E. coli FhuA protein. Surface expression of the fusion proteins was demonstrated by functional assays and by FACS analysis. The fibronectin-binding motifs were shown to mediate entry of the bacteria into non-phagocytic eukaryotic cells and brought about the preferential selection of these bacteria over E. coli expressing parental FhuA, with an enrichment of 100000-fold. Four entry sequences were selected and identified using an S. aureus library of peptides displayed in the FhuA protein on the surface of E. coli. These sequences included novel entry motifs as well as integrin-binding Arg-Gly-Asp (RGD) motifs and promoted a high degree of bacterial entry. Bacterial surface display is thus a powerful tool to effectively select and identify entry peptide motifs.