E495 is the most abundant protease secreted by the Arctic sea-ice bacterium Pseudoalteromonas sp. SM495. As a thermolysin family metalloprotease, E495 was found to have multiple active forms in the culture of strain SM495. E495-M (containing only the catalytic domain) and E495-M-C1 (containing the catalytic domain and one PPC domain) were two stable mature forms, and E495-M-C1-C2 (containing the catalytic domain and two PPC domains) might be an intermediate. Compared to E495-M, E495-M-C1 had similar affinity and catalytic efficiency to oligopeptides, but higher affinity and catalytic efficiency to proteins. The PPC domains from E495 were expressed as GST-fused proteins. Both of the recombinant PPC domains were shown to have binding ability to proteins C-phycocyanin and casein, and domain PPC1 had higher affinity to C-phycocyanin than domain PPC2. These results indicated that the domain PPC1 in E495-M-C1 could be helpful in binding protein substrate, and therefore, improving the catalytic efficiency. Site-directed mutagenesis on the PPC domains showed that the conserved polar and aromatic residues, D26, D28, Y30, Y/W65, in the PPC domains played key roles in protein binding. Our study may shed light on the mechanism of organic nitrogen degradation in the Arctic sea ice.