The Truncated Nonsmooth Newton Multigrid (TNNMG) method is a well-established method for the solution of strictly convex block-separably nondifferentiable minimization problems. It achieves multigrid-like performance even for non-smooth nonlinear problems, while at the same time being globally convergent and without employing penalty parameters. We show that the algorithm can be applied to the primal problem of classical small-strain elastoplasticity with hardening. Numerical experiments show that the method is considerably faster than classical predictor–corrector methods. Indeed, solving an entire increment problem with TNNMG can take less time than a single predictor–corrector iteration for the same problem. At the same time, memory consumption is reduced considerably, in particular for three-dimensional problems. Since the algorithm does not rely on differentiability of the objective functional, nonsmooth yield laws can be easily incorporated. The method is closely related to a predictor–corrector scheme with a consistent tangent predictor and line search. We explain the algorithm, prove global convergence, and show its efficiency using standard benchmarks from the literature.