Abstract Background Repetitive extragenic palindromic elements (REPs) constitute a group of bacterial genomic repeats known for their high abundance and several roles in host cells´ physiology. We analyzed the phylogenetic distribution of particular REP classes in genomic sequences of sixty-three bacterial strains belonging to the Pseudomonas fluorescens species complex and ten strains of Stenotrophomonas sp., in order to assess intraspecific REP diversity and to gain insight into long-term REP evolution. Results Based on proximity to RAYT (REP-associated tyrosine transposase) genes, twenty-two and thirteen unique REP classes were determined in fluorescent pseudomonads and stenotrophomonads, respectively. In stenotrophomonads, REP elements were typically found in tens or a few hundred copies per genome. REPs of fluorescent pseudomonads were generally more numerous, occurring in hundreds or even over a thousand perfect copies of particular REP class per genome. REP sequences showed highly heterogeneous distribution. The abundances of REP classes roughly followed host strains´ phylogeny, differing markedly among individual clades. High abundances of particular REP classes appeared to depend on the presence of the cognate RAYT gene, and deviations from this state could be attributed to recent or ancient mutations of rayt -flanking REPs, or RAYT loss. RAYTs of both studied bacterial groups are monophyletic, and their cognate REPs show species-specific characteristics, suggesting shared evolutionary history of REPs, RAYTs and their hosts. Conclusions The results of our large-scale analysis show that REP elements constitute intriguingly dynamic components of genomes of fluorescent pseudomonads and stenotrophomonads, and indicate that REP diversification and proliferation are ongoing processes. High numbers of REPs have apparently been retained during the entire evolutionary time since the establishment of these two bacterial lineages, probably because of their beneficial effect on host long-term fitness. REP elements in these bacteria represent a suitable platform to study the interplay between repeated elements, their mobilizers and host bacterial cells.