An extension of the two-step staggered time discretization of linear elastodynamics in stress-velocity form to systems involving internal variables subjected to a possibly non-linear dissipative evolution is proposed. The original scheme is thus enhanced by another step for the internal variables which, in general, is implicit, although even this step might be explicit if no spatial gradients of the internal variables are involved. Using an abstract Banach-space formulation, a priori estimates and convergence are proved under a CFL condition. The developed three-step scheme finds applications in various problems of continuum mechanics at small strain. Here, we consider in particular plasticity, viscoelasticity (creep), diffusion in poroelastic media, and damage.