Site-specific modification of proteins has important applications in biological research and drug development. Reactive tags such as azide, alkyne, and tetrazine have been used extensively to achieve the abovementioned goal. However, bulky side-chain "ligation scars" are often left after the labeling and may hinder the biological application of such engineered protein products. Conjugation chemistry via dehydroalanine (Dha) may provide an opportunity for "traceless" ligation because the activated alkene moiety on Dha can then serve as an electrophile to react with radicalophile, thiol/amine nucleophile, and reactive phosphine probe to introduce a minimal linker in the protein post-translational modifications. In this report, we present a mild and highly efficient enzymatic approach to incorporate Dha with phosphothreonine/serine lyases, OspF and SpvC. These lyases originally catalyze an irreversible elimination reaction that converts a doubly phosphorylated substrate with phosphothreonine (pT) or phosphoserine (pS) to dehydrobutyrine (Dhb) or Dha. To generate a simple monophosphorylated tag for these lyases, we conducted a systematic approach to profile the substrate specificity of OspF and SpvC using peptide arrays and self-assembled monolayers for matrix-assisted laser desorption/ionization mass spectrometry. The optimized tag, [F/Y/W]-pT/pS-[F/Y/W] (where [F/Y/W] indicates an aromatic residue), results in a ∼10-fold enhancement of the overall peptide labeling efficiency via Dha chemistry and enables the first demonstration of protein labeling as well as live cell labeling with a minimal ligation linker via enzyme-mediated incorporation of Dha.