Many agarolytic microorganisms have been found in marine environments, such as the genera Pseudomonas, Pseudoalteromonas, Streptomyces, Alteromonas, Microscilla, Vibrio, Cytophaga, and Bacillus. Known β-agarases are classified into three glycoside hydrolase (GH) families, 16, 50, and 86. Agarases in GH-16 family usually degrade agarose and neoagarohexaose (N6) to yield neoagarotetraose (N4) as a main product. The enzymes in GH-50 family hydrolyze agarose and N4 to yield neoagarobiose (N2) or N6 to yield N4 and N2 as the predominant products. The enzyme in GH-86 family has not yet purified and characterized. We isolated agar-degrading Microbulbifer and Microbulbifer-like bacteria from samples of deep-sea sediments. The β-agarases that they produced were all grouped into GH-16 family. The enzymes are thermostable and resistant to metal ions, chelating reagents, and surfactants, the properties of which fulfill essential requirements for use in various industries.