Carnobacterium maltaromaticum is a well-known pathogen of bony fish. More recently, C. maltaromaticum have been isolated from the brain and inner ear of disorientated and stranded common thresher (Alopias vulpinus) and salmon shark (Lamna ditropis). While thresher shark strandings are recent, salmon sharks have been stranding for decades, suggesting a long-term association between C. maltaromaticum and sharks. Interestingly, some strains of C. maltaromaticum are used by the food industry for their probiotic and antimicrobial activity. Here, we sequenced the genome of 9 C. maltaromaticum strains (SK-isolates) from diseased common thresher and salmon sharks and compared them to other C. maltaromaticum strains in order to identify the genomic signatures that differentiate the disease-associated from the innocuous C. maltaromaticum isolates. SK strains formed a monophyletic clade, with a conserved gene repertoire, and shared a high degree of pseudogenization even though isolates were from different shark species, locations, and across years. In addition, these strains displayed few virulence associated genes and unique genomic regions, some resulting from horizontal gene transfer. The association of diseased sharks and SK strains suggests their role as potential pathogens. Although the high degree of pseudogenization suggests a transition to a host-adapted lifestyle, a set of conserved functional genes highlights the need of essential functions required for a host-independent life style. Globally, this work identifies specific genomic signatures of C. maltaromaticum strains isolated from infected sharks, provides the framework to elucidate the role of SK strains in the development of the disease in sharks, and further investigate the dissemination of SK strains in populations of wild fish.