Aeromonas spp. are among the most ubiquitous microorganisms, as they have been isolated from different environmental niches including waters, soil, as well as wounds and digestive tracts of poikilothermic animals and humans. Although much attention has been paid to the pathogenicity of Aeromonads, the role of these bacteria in environmentally important processes, such as transformation of heavy metals, remains to be discovered. Therefore, the aim of this study was a detailed genomic characterization of Aeromonas sp. O23A, the first representative of this genus capable of dissimilatory arsenate reduction. The strain was isolated from microbial mats from the Zloty Stok mine (SW Poland), an environment strongly contaminated with arsenic. Previous physiological studies indicated that O23A may be involved in both mobilization and immobilization of this metalloid in the environment. To discover the molecular basis of the mechanisms behind the observed abilities, the genome of O23A (∼5.0 Mbp) was sequenced and annotated, and genes for arsenic respiration, heavy metal resistance (hmr) and other phenotypic traits, including siderophore production, were identified. The functionality of the indicated gene modules was assessed in a series of minimal inhibitory concentration analyses for various metals and metalloids, as well as mineral dissolution experiments. Interestingly, comparative analyses revealed that O23A is related to a fish pathogen Aeromonas salmonicida subsp. salmonicida A449 which, however, does not carry genes for arsenic respiration. This indicates that the dissimilatory arsenate reduction ability may have been lost during genome reduction in pathogenic strains, or acquired through horizontal gene transfer. Therefore, particular emphasis was placed upon the mobilome of O23A, consisting of four plasmids, a phage, and numerous transposable elements, which may play a role in the dissemination of hmr and arsenic metabolism genes in the environment. The obtained results indicate that Aeromonas sp. O23A is well-adapted to the extreme environmental conditions occurring in the Zloty Stok mine. The analysis of genome encoded traits allowed for a better understanding of the mechanisms of adaptation of the strain, also with respect to its presumable role in colonization and remediation of arsenic-contaminated waters, which may never have been discovered based on physiological analyses alone.