A Gram-negative, aerobic, motile, rod-shaped, agarolytic bacterium, designated as H7, was isolated from a coastal seawater sample. This strain grows at pH 6.0-8.0, temperature of 15-40 °C, and at an NaCl concentration of 1-7% (w/v). Ubiquinone-8 was the predominant respiratory quinone, and the DNA G+C content was 45.82 mol%. Analysis of the 16S rRNA sequence suggests that strain H7 belongs to the genus Pseudoalteromonas. DNA-DNA hybridization analysis showed DNA relatedness of as low as 55.42 and 40.27% with its nearest phylogenetic neighbors Pseudoalteromonas atlantica IAM12927T and Pseudoalteromonas espejiana NCIMB2127T, respectively, which led us to name H7 Pseudoalteromonas hodoensis sp. nov. The type strain is H7T (=DSM25967T=KCTC23887T). An agarase (AgaA7) was purified to homogeneity from the cell-free culture broth of H7 through many steps of chromatography. Purified AgaA7 had an apparent molecular weight of 35 kDa, with a distinct NH2-terminal sequence of Ala-Asp-Ala-Thr-X-Pro (X, any amino acid) from the reported proteins, implying that it is a novel enzyme. The optimum pH and temperature for agarase activity were 7.0 and 45 °C, respectively. Thin-layer chromatography analysis, mass spectrometry, and enzyme assay using p-nitrophenyl-α/β-D-galactopyranoside revealed that AgaA7 is both an exo- and endo-type β-agarase that degrades agarose into neoagarotetraose, neoagarohexaose, and neoagarooctaose (minor).