  We study the spectra of $N\times N$ Toeplitz band matrices perturbed by small
complex Gaussian random matrices, in the regime $N\gg 1$. We prove a
probabilistic Weyl law, which provides an precise asymptotic formula for the
number of eigenvalues in certain domains, which may depend on $N$, with
probability sub-exponentially (in $N$) close to $1$. We show that most
eigenvalues of the perturbed Toeplitz matrix are at a distance of at most
$\mathcal{O}(N^{-1+\varepsilon})$, for all $\varepsilon >0$, to the curve in
the complex plane given by the symbol of the unperturbed Toeplitz matrix.
