We have compared genomes of Alteromonas macleodii “deep ecotype” isolates from two deep Mediterranean sites and two surface samples from the Aegean and the English Channel. A total of nine different genomes were analyzed. They belong to five clonal frames (CFs) that differ among them by approximately 30,000 single-nucleotide polymorphisms (SNPs) over their core genomes. Two of the CFs contain three strains each with nearly identical genomes (∼100 SNPs over the core genome). One of the CFs had representatives that were isolated from samples taken more than 1,000 km away, 2,500 m deeper, and 5 years apart. These data mark the longest proven persistence of a CF in nature (outside of clinical settings). We have found evidence for frequent recombination events between or within CFs and even with the distantly related A. macleodii surface ecotype. The different CFs had different flexible genomic islands. They can be classified into two groups; one type is additive, that is, containing different numbers of gene cassettes, and is very variable in short time periods (they often varied even within a single CF). The other type was more stable and produced the complete replacement of a genomic fragment by another with different genes. Although this type was more conserved within each CF, we found examples of recombination among distantly related CFs including English Channel and Mediterranean isolates.