For random walk on a graph, the cover time $T$ is the number of steps required to visit every vertex at least once. We prove the following large deviation bound for the cover time: For every $A>0$ and $d>0$ there is a constant $c>0$ such that for all $n$ and graphs on $n$ vertices of maximum degree $d$, we have $P(T < An) < \exp(-cn)$. \\ \noindent Joint work with Itai Benjamini and Ori Gurel-Gurevich.