We are interested in finding a nonlinear polynomial P on \(\mathbb {R}^n\) that solves the minimal surface equation. Even though no explicit solution is found in this article, we investigate constraints that a polynomial solution must obey. We first prove a structure theorem on such polynomials. We show that the highest degree term \(P_m\) must factor as \(p^kQ_m\) where k is odd, p is irreducible, and \(Q_m\ge 0\) on \(\mathbb {R}^n\) with \(\{Q_m=0\}\subset \{p=0\}\cap \{\nabla p=0\}\) . Moreover, the level sets of \(P_m\) are all area-minimizing and the unique tangent cone of \({{\,\textrm{graph}\,}}P\) at infinity is \(\{p=0\}\times \mathbb {R}\) . If \(k\ge 3\) , we know further that lower order terms down to some degree are divisible by p. We also show that P must contain terms of both high and low degree. In particular, it cannot be homogeneous. As a consequence of the structure theorem, we get degree estimates for polynomial solutions. We have \(\deg P\ge 4\) by ruling out cubic polynomial solutions. Using an extended eigenvalue estimate on the Jacobi operator by Zhu [39], we are able to show that \(\mu _n^-< \deg p +k^{-1}\deg Q_m< \mu _n^+\) where \(\mu _n^\pm =\frac{n-1\pm \sqrt{(n-3)^2-4(n-2)}}{2}\) . Finally, we prove that \(\{p=0\}\) cannot be an isoparametric minimal cone. We also show that for a nonlinear polynomial solution on \(\mathbb {R}^8\) , we have \(\deg p=3\) and that \(\{p=0\}\) is an area-minimizing but not strictly minimizing cone in \(\mathbb {R}^8\) . These results give strong restrictions on possible polynomial solutions to the minimal surface equation.