The ovine footrot pathogen, Dichelobacter nodosus, secretes three subtilisin-like proteases that play an important role in the pathogenesis of footrot through their ability to mediate tissue destruction. Virulent and benign strains of D. nodosus secrete the basic proteases BprV and BprB, respectively, with the catalytic domain of these enzymes having 96% sequence identity. At present, it is not known how sequence variation between these two putative virulence factors influences their respective biological activity. We have determined the high resolution crystal structures of BprV and BprB. These data reveal that that the S1 pocket of BprV is more hydrophobic but smaller than that of BprB. We show that BprV is more effective than BprB in degrading extracellular matrix components of the host tissue. Mutation of two residues around the S1 pocket of BprB to the equivalent residues in BprV dramatically enhanced its proteolytic activity against elastin substrates. Application of a novel approach for profiling substrate specificity, the Rapid Endopeptidase Profiling Library (REPLi) method, revealed that both enzymes prefer cleaving after hydrophobic residues (and in particular P1 leucine) but that BprV has more restricted primary substrate specificity than BprB. Furthermore, for P1 Leu-containing substrates we found that BprV is a significantly more efficient enzyme than BprB. Collectively, these data illuminate how subtle changes in D. nodosus proteases may significantly influence tissue destruction as part of the ovine footrot pathogenesis process.