A total of 92 marine bacteria belonging to Pseudomonas, Pseudoalteromonas, Psychrobacter, and Shewanella were first screened for their proteolytic activity. In total, four Pseudomonas strains belonging to Ps. fluorescens, Ps. fragi, Ps. gessardii, and Ps. marginalis; 14 Pseudoalteromonas strains belonging to Psa. arctica, Psa. carrageenovora, Psa. elyakovii, Psa. issachenkonii, Psa. rubra, Psa. translucida, and Psa. tunicata; and two Shewanella strains belonging to S. baltica and S. putrefaciens were identified to have a weak to high proteolytic activity (from 478 to 4445 mU/mg trypsin equivalent) against skim milk casein as protein source. Further chitinolytic activity screening based on these 20 proteolytic strains using colloidal chitin yielded five positive strains which were tested against three different chitin substrates in order to determine the various types of chitinases. Among the strains that can produce both proteases and chitinases, Psa. rubra DSM 6842T expressed not only the highest proteolytic activity (2558 mU/mg trypsin equivalent) but also the highest activity of exochitinases, specifically, β-N-acetylglucosaminidase (6.33 mU/107 cfu) as well. We anticipate that this strain can be innovatively applied to the valorization of marine crustaceans side streams.