Dimethylsulfoniopropionate (DMSP) is one of the most important organic sulfur compounds in the ocean and plays a key role in polar carbon and sulfur cycles. Sulfitobacter sp. M13, a Gram-negative and aerobic bacterium, was isolated from the melting sea ice in the central Arctic Ocean. Here, we report the complete genome sequence of strain M13 and its genomic characteristics to catabolize DMSP. The genome of strain M13 contains one circular chromosome (3,987,975 bp) and five circular plasmids. Genomic analysis showed that strain M13 contained genes encoding DMSP lyases and the downstream enzymes involved in the DMSP cleavage pathway, indicating that it possesses the potential ability to participate in DMSP metabolism. These findings enhance our understanding of the global sulfur cycling driven by bacteria and reveal the potential strategy of the strain M13 to adapt the extreme environments of Arctic Ocean.