Biotinylation creates a sensitive and specific tag for purification and detection of target proteins. The E. coli protein-biotin ligase BirA biotinylates a lysine within a synthetic biotin acceptor peptide (AP) and allow for specific tagging of proteins fused to the AP. The approach is not applicable to unmodified proteins, and we sought to develop an effective selection system that could form the basis for directed evolution of novel BirA variants with specificity towards unmodified proteins. The system was based on bacterial display of a target peptide sequence, which could be biotinylated by cytosolic BirA variants before being displayed on the surface. In a model selection, the bacterial display system accomplished >1.000.000 enrichment in a single selection step. A randomly mutated BirA library was used to identify novel variants. Bacteria displaying peptide sequences from 13 out of 14 tested proteins were strongly enriched after 3-5 selection rounds. Moreover, a clone selected for biotinylation of a C-terminal peptide from red-fluorescent protein TagRFP showed biotinylation of the native protein. Thus, active BirA variants with novel activity are effectively isolated with our bacterial display system and provides a basis for the development of BirA variants for site-selective biotinylation.