  Consider a random walk $S=(S_n:n\geq 0)$ that is ``perturbed'' by a
stationary sequence $(\xi_n:n\geq 0)$ to produce the process
$(S_n+\xi_n:n\geq0)$. This paper is concerned with computing the distribution
of the all-time maximum $M_{\infty}=\max \{S_k+\xi_k:k\geq0\}$ of perturbed
random walk with a negative drift. Such a maximum arises in several different
applications settings, including production systems, communications networks
and insurance risk. Our main results describe asymptotics for
$\mathbb{P}(M_{\infty}>x)$ as $x\to\infty$. The tail asymptotics depend greatly
on whether the $\xi_n$'s are light-tailed or heavy-tailed. In the light-tailed
setting, the tail asymptotic is closely related to the Cram\'{e}r--Lundberg
asymptotic for standard random walk.
