We study the spectra of general $N\times N$ Toeplitz matrices given by symbols in the Wiener Algebra perturbed by small complex Gaussian random matrices, in the regime $N\gg 1$. We prove an asymptotic formula for the number of eigenvalues of the perturbed matrix in smooth domains. We show that these eigenvalues follow a Weyl law with probability sub-exponentially close to $1$, as $N\gg1$, in particular that most eigenvalues of the perturbed Toeplitz matrix are close to the curve in the complex plane given by the symbol of the unperturbed Toeplitz matrix.