A method is described to allow searches for transonic aeroelastic instability of realistically sized aircraft models in multidimensional parameter spaces when computational fluid dynamics are used to model the aerodynamics. Aeroelastic instability is predicted from a small nonlinear eigenvalue problem. The approximation of the computationally expensive interaction term modeling the fluid response is formulated to allow the automated and blind search for aeroelastic instability. The approximation uses a kriging interpolation of exact numerical samples covering the parameter space. The approach, demonstrated for the Goland wing and the multidisciplinary optimization transport wing, results in stability analyses over whole flight envelopes at an equivalent cost of several steady-state simulations.