Remineralization of organic matter in deep-sea sediments is important in oceanic biogeochemical cycles, and bacteria play a major role in this process. Shewanella violacea DSS12 is a psychrophilic and piezophilic gamma-proteobacterium that was isolated from the surface layer of deep sea sediment at a depth of 5110 m. Here, we report the complete genome sequence of S. violacea and comparative analysis with the genome of S. oneidensis MR-1, isolated from sediments of a freshwater lake. Unlike S. oneidensis, this deep-sea Shewanella possesses very few terminal reductases for anaerobic respiration and no c-type cytochromes or outer membrane proteins involved in respiratory Fe(iii) reduction, which is characteristic of most Shewanella species. Instead, the S. violacea genome contains more terminal oxidases for aerobic respiration and a much greater number of putative secreted proteases and polysaccharases, in particular, for hydrolysis of collagen, cellulose and chitin, than are encoded in S. oneidensis. Transporters and assimilatory reductases for nitrate and nitrite, and nitric oxide-detoxifying mechanisms (flavohemoglobin and flavorubredoxin) are found in S. violacea. Comparative analysis of the S. violacea genome revealed the respiratory adaptation of this bacterium to aerobiosis, leading to predominantly aerobic oxidation of organic matter in surface sediments, as well as its ability to efficiently use diverse organic matter and to assimilate inorganic nitrogen as a survival strategy in the nutrient-poor deep-sea floor.