We derive the long-time asymptotics for the Toda shock problem using the nonlinear steepest descent analysis for oscillatory Riemann--Hilbert factorization problems. We show that the half plane of space/time variables splits into five main regions: The two regions far outside where the solution is close to free backgrounds. The middle region, where the solution can be asymptotically described by a two band solution, and two regions separating them, where the solution is asymptotically given by a slowly modulated two band solution. In particular, the form of this solution in the separating regions verifies a conjecture from Venakides, Deift, and Oba from 1991.