We study the Integrated Density of States of one-dimensional random operators acting on $\ell^2(\mathbb Z)$ of the form $T + V_ω$ where $T$ is a Laurent (also called bi-infinite Toeplitz) matrix and $V_ω$ is an Anderson potential generated by i.i.d. random variables. We assume that the operator $T$ is associated to a bounded, Hölder-continuous symbol $f$, that attains its minimum at a finite number of points. We allow for $f$ to attain its minima algebraically. The resulting operator $T$ is long-range with weak (algebraic) off-diagonal decay. We prove that this operator exhibits Lifshitz tails at the lower edge of the spectrum with an exponent given by the Integrated Density of States of $T$ at the lower spectral edge. The proof relies on generalizations of Dirichlet-Neumann bracketing to the long-range setting and a generalization of Temple's inequality to degenerate ground state energies.