Prokaryotic proteins must be deformylated before the removal of their first methionine. Peptide deformylase (PDF) is indispensable and guarantees this mechanism. Recent metagenomics studies revealed new idiosyncratic PDF forms as the most abundant family of viral sequences. Little is known regarding these viral PDFs, including the capacity of the corresponding encoded proteins to ensure deformylase activity. We provide here the first evidence that viral PDFs, including the shortest PDF identified to date, Vp16 PDF, display deformylase activity in vivo, despite the absence of the key ribosome-interacting C-terminal region. Moreover, characterization of phage Vp16 PDF underscores unexpected structural and molecular features with the C-terminal Isoleucine residue significantly contributing to deformylase activity both in vitro and in vivo. This residue fully compensates for the absence of the usual long C-domain. Taken together, these data elucidate an unexpected mechanism of enzyme natural evolution and adaptation within viral sequences.