Active Appearance Models (AAMs) are statistical models of shape and appearance widely used in computer vision to detect landmarks on objects like faces. Fitting an AAM to a new image can be formulated as a non-linear least-squares problem which is typically solved using iterative methods. Owing to its efficiency, Gauss-Newton optimization has been the standard choice over more sophisticated approaches like Newton. In this paper, we show that the AAM problem has structure which can be used to solve efficiently the original Newton problem without any approximations. We then make connections to the original Gauss-Newton algorithm and study experimentally the effect of the additional terms introduced by the Newton formulation on both fitting accuracy and convergence. Based on our derivations, we also propose a combined Newton and Gauss-Newton method which achieves promising fitting and convergence performance. Our findings are validated on two challenging in-the-wild data sets.