Proteases in the M23 family have specific activities toward elastin and bacterial peptidoglycan. The peptidoglycan-degrading property makes these proteases have potential as novel antimicrobials. Because M23 proteases cannot be maturely expressed in Escherichia coli, it is significant to improve the production of these enzymes in their wild strains. Pseudoalterin is a new M23 protease secreted by the deep-sea bacterium Pseudoalteromonas sp. CF6-2. In this study, the fermentation conditions of strain CF6-2 for pseudoalterin production were optimized using single factor experiments and response surface methodology to improve the enzyme yield. To reduce the fermentation cost, bovine artery powder instead of elastin was determined as a cheap and efficient inducer. Based on single factor experiments, artery powder content, culture temperature and culture time were determined as the main factors influencing pseudoalterin production and were further optimized by the central composite design. The optimal values of these factors were determined as: artery powder of 1.2%, culture temperature of 20.17 °C and culture time of 28.04 h. Under the optimized conditions, pseudoalterin production reached 100.02 ± 9.0 U/mL, more than twice of that before optimization. These results lay a good foundation for developing the biotechnological potential of pseudoalterin.