We develop a formalism to treat higher order (nonlinear) metric perturbations of the Kerr spacetime in a Teukolsky framework. We first show that solutions to the linearized Einstein equation with nonvanishing stress tensor can be decomposed into four terms: a pure gauge term, an infinitesimal perturbation of the black hole mass and spin, a perturbation arising from a Hertz potential, and a “corrector tensor.” The Hertz potential is a solution to the spin -2 Teukolsky equation with a source. This source, as well as the tetrad components of the corrector tensor, are obtained by solving certain decoupled ordinary differential equations involving the stress tensor. In outgoing Kerr-Newman coordinates, solving these ordinary differential equations reduces simply to integrations in the r coordinate. Since higher order perturbations are subject to a linearized Einstein equation with a stress tensor obtained from the lower order perturbations, our method applies iteratively to higher order metric perturbations. We discuss possible applications, including to analyze perturbations generated by a pointlike body in Kerr.