In this paper, we show that the Newton polytope of an observation $Y$ from a two-dimensional hidden Markov model\linebreak (2D HMM) lies in a three-dimensional subspace of its ambient eight-dimensional space, whose vertices correspond to the most likely explanations (``hidden'' states) for $Y$ given the model. For each Newton polytope, there exists a set of ``essential'' vertices, which form a skeleton for the polytope. All observations in the same orbit (identical under translations, rotations, and transpositions) have the same Newton polytope. Our main conjecture is that the maximal number of vertices of any Newton polytope is of order $n^2$