We derive the equations governing the linear stability of Kerr-Newman spacetime to coupled electromagnetic-gravitational perturbations. The equations generalize the celebrated Teukolsky equation for curvature perturbations of Kerr, and the Regge-Wheeler equation for metric perturbations of Reissner-Nordstrom. Because of the apparent indissolubility of the coupling between the spin-1 and spin-2 fields, as put by Chandrasekhar, the stability of Kerr-Newman spacetime can not be obtained through standard decomposition in modes. Due to the impossibility to decouple the modes of the gravitational and electromagnetic fields, the equations governing the linear stability of Kerr-Newman have not been previously derived. Using a tensorial approach that was applied to Kerr, we produce a set of generalized Regge-Wheeler equations for perturbations of Kerr-Newman, which are suitable for the study of linearized stability by physical space methods. The physical space analysis overcomes the issue of coupling of spin-1 and spin-2 fields and represents the first step towards an analytical proof of the stability of the Kerr-Newman black hole.