As previously reported, P. aeruginosa genes PA2077 and PA2078 code for 10S-DOX (10S-Dioxygenase) and 7,10-DS (7,10-Diol Synthase) enzymes involved in long-chain fatty acid oxygenation through the recently described oleate-diol synthase pathway. Analysis of the amino acid sequence of both enzymes revealed the presence of two heme-binding motifs (CXXCH) on each protein. Phylogenetic analysis showed the relation of both proteins to bacterial di-heme cytochrome c peroxidases (Ccps), similar to Xanthomonas sp. 35Y rubber oxidase RoxA. Structural homology modelling of PA2077 and PA2078 was achieved using RoxA (pdb 4b2n) as a template. From the 3D model obtained, presence of significant amino acid variations in the predicted heme-environment was found. Moreover, the presence of palindromic repeats located in enzyme-coding regions, acting as protein evolution elements, is reported here for the first time in P. aeruginosa genome. These observations and the constructed phylogenetic tree of the two proteins, allow the proposal of an evolutionary pathway for P. aeruginosa oleate-diol synthase operon. Taking together the in silico and in vivo results obtained we conclude that enzymes PA2077 and PA2078 are the first described members of a new subfamily of bacterial peroxidases, designated as Fatty acid-di-heme Cytochrome c peroxidases (FadCcp).