Recent studies have shown significant differences in migration mechanisms between two- and three-dimensional environments. While experiments have suggested a strong dependence of in vivo migration on both structure and proteolytic activity, the underlying biophysics of such dependence has not been studied adequately. In addition, the existing models of persistent random walk migration are primarily based on two-dimensional movement and do not account for the effect of proteolysis or matrix inhomogeneity. Using lattice Monte Carlo methods, we present a model to study the role of matrix metallo-proteases (MMPs) on directional persistence and speed. The simulations account for a given cell's ability to deform as well as to digest the matrix as the cell moves in three dimensions. Our results show a bimodal dependence of speed and persistence on matrix pore size and suggest high sensitivity on MMP activity, which is in very good agreement with experimental studies carried out in 3D matrices.