  We define the empirical spectral distribution (ESD) of a random matrix
polynomial with invertible leading coefficient, and we study it for complex $n
\times n$ Gaussian monic matrix polynomials of degree $k$. We obtain exact
formulae for the almost sure limit of the ESD in two distinct scenarios: (1) $n
\rightarrow \infty$ with $k$ constant and (2) $k \rightarrow \infty$ with $n$
constant. The main tool for our approach is the replacement principle by Tao,
Vu and Krishnapur. Along the way, we also develop some auxiliary results of
potential independent interest: we slightly extend a result by B\"{u}rgisser
and Cucker on the tail bound for the norm of the pseudoinverse of a non-zero
mean matrix, and we obtain several estimates on the singular values of certain
structured random matrices.
