This paper proposes a stability verification method for systems controlled by an early terminated first-order method (e.g., an MPC problem approximately solved by a fixed number of iterations of the fast gradient method). The method is based on the observation that each step of the vast majority of first-order methods is characterized by a Karush-Kuhn-Tucker (KKT) system which (provided that all data are polynomial) is a basic semialgebraic set; M steps of a first-order method is then characterized by a basic semialgebraic set given by the intersection of M coupled KKT systems. Using sum-of-squares techniques, one can then search for a polynomial Lyapunov function that decreases between two consecutive time instances for all control inputs belonging to this coupled KKT system. The proposed method applies to nonlinear dynamical systems described by polynomial (or trigonometric) data affected by a (possibly state-dependent) disturbance; in particular the method is not restricted to linear systems and/or convex cost functions. To the best of the authors' knowledge, this is the first verification approach for early terminated optimization schemes with this level of generality.