N-terminal formylation of ribosome-synthesized polypeptides is assumed to be among the most conserved features that distinguish the eubacterial line of descent from other living phyla. In order to assess the ancientness of this trait, def genes encoding polypeptide deformylase were characterized from four eubacterial species, Lactococcus lactis, Bacillus subtilis, Calothrix PCC7601 and Thermotoga maritima, taking advantage of the conditional viability of the def mutants of Escherichia coli. Altogether, eight sequences of polypeptide deformylase have been obtained from all the eubacterial sources which were investigated, either through systematic genome sequence analysis or through genetic screening, yielding a highly homologous family. A gene putatively encoding Met-tRNAi formyltransferase, fmt, was found downstream of the deformylase gene except in L. lactis, Mycoplasma genitalium, Calothrix PCC7601 and T. maritima. These results argue strongly for the ancestral character of N-terminal formylation in eubacteria. Most of the wide deviations of amino acid usage observed in def- and fmt-encoded proteins among species is best accounted for by the nucleotide composition of genomes. Furthermore, the species of origin of each protein appears to be more recognizable than its function, considering only its amino acid composition.