We report the results of molecular dynamics simulations of stress relaxation tests in athermal viscous soft sphere packings close to their unjamming transition. By systematically and simultaneously varying both the amplitude of the applied strain step and the pressure of the initial condition, we access both linear and nonlinear response regimes and control the distance to jamming. Stress relaxation in viscoelastic solids is characterized by a relaxation time τ∗ that separates short time scales, where viscous loss is substantial, from long time scales, where elastic storage dominates and the response is essentially quasistatic. We identify two distinct plateaus in the strain dependence of the relaxation time, one each in the linear and nonlinear regimes. The height of both plateaus scales as an inverse power law with the distance to jamming. By probing the time evolution of particle velocities during relaxation, we further identify a correlation between mechanical relaxation in the bulk and the degree of non-affinity in the particle velocities on the micro scale.