We give the first polynomial-time algorithm for solving the linear complementarity problem with tridiagonal or, more generally, Hessenberg P-matrices.