Actin protrusion dynamics plays an important role in the regulation of three-dimensional (3D) cell migration. Cells form protrusions that adhere to the surrounding extracellular matrix (ECM), mechanically probe the ECM and contract in order to displace the cell body. This results in cell migration that can be directed by the mechanical anisotropy of the ECM. However, the subcellular processes that regulate protrusion dynamics in 3D cell migration are difficult to investigate experimentally and therefore not well understood. Here, we present a computational model of cell migration through a degradable viscoelastic ECM. This model is a 2D representation of 3D cell migration. The cell is modeled as an active deformable object that captures the viscoelastic behavior of the actin cortex and the subcellular processes underlying 3D cell migration. The ECM is regarded as a viscoelastic material, with or without anisotropy due to fibrillar strain stiffening, and modeled by means of the meshless Lagrangian smoothed particle hydrodynamics (SPH) method. ECM degradation is captured by local fluidization of the material and permits cell migration through the ECM. We demonstrate that changes in ECM stiffness and cell strength affect cell migration and are accompanied by changes in number, lifetime and length of protrusions. Interestingly, directly changing the total protrusion number or the average lifetime or length of protrusions does not affect cell migration. A stochastic variability in protrusion lifetime proves to be enough to explain differences in cell migration velocity. Force-dependent adhesion disassembly does not result in faster migration, but can make migration more efficient. We also demonstrate that when a number of simultaneous protrusions is enforced, the optimal number of simultaneous protrusions is one or two, depending on ECM anisotropy. Together, the model provides non-trivial new insights in the role of protrusions in 3D cell migration and can be a valuable contribution to increase the understanding of 3D cell migration mechanics.