Protein trans-splicing mediated by split inteins is a powerful technique for site-specific protein modification. Despite recent developments there is still an urgent need for ultra-small high-affinity intein tags for in vitro and in vivo approaches. To date, only very few in-cell applications of protein trans-splicing have been reported, all limited to C-terminal protein modifications. Here, we developed a strategy for covalent N-terminal intein-mediated protein labeling at (sub) nanomolar probe concentrations. Combined with a minimal synthetic lock-and-key element, the affinity between the intein fragments was increased more than 50-fold to 10 nM. Site-specific and efficient 'traceless' protein modification by high-affinity trans-splicing is demonstrated at nanomolar concentrations in living mammalian cells.