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ü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.