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 linear 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 takes less time than a single predictor-corrector iteration for the same problem. Since the algorithm does not rely on differentiability of the objective functional, nonsmooth yield functions like the Tresca yield function 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 a standard benchmark from the literature.