Biotin is an attractive post-translational modification of proteins that provides a powerful tag for the isolation and detection of protein. Enzymatic biotinylation by the E. coli biotin-protein ligase BirA is highly specific and allows for the biotinylation of target proteins in their native environment; however, the current usage of BirA mediated biotinylation requires the presence of a synthetic acceptor peptide (AP) in the target protein. Therefore, its application is limited to proteins that have been engineered to contain the AP. The purpose of the present protocol is to use the bacterial display of a peptide derived from an unmodified target protein to select for BirA variants that biotinylates the peptide. The system is based on a single plasmid that allows for the co-expression of BirA variants along with a scaffold for the peptide display on the bacterial surface. The protocol describes a detailed procedure for the incorporation of the target peptide into the display scaffold, creation of the BirA library, selection of active BirA variants and initial characterization of the isolated BirA variants. The method provides a highly effective selection system for the isolation of novel BirA variants that can be used for the further directed evolution of biotin-protein ligases that biotinylate a native protein in complex solutions.