We demonstrate a nonlinear optical resonator that tunes itself onto resonance with an input beam. In a monolithic Fabry-Perot cavity implemented in rubidium-doped periodically poled potassium titanyl phosphate, an intensity-dependent refractive index produces line pulling by multiple free-spectral ranges (FSRs). In this condition, the cavity passively maintains optical resonance in the face of FSR-scale excursions of the drive laser frequency: when one resonant operating point becomes unstable, the resonator rapidly transitions to another resonant operating point. We demonstrate stable second-harmonic generation with no active feedback to the laser or cavity. The self-tuning effect appears to be supported by a very strong, previously unreported optical nonlinearity.