Atomic inner-shell relaxation dynamics were measured at the free-electron laser in Hamburg, FLASH, delivering 92 eV pulses. The decay of 4d core holes created in xenon was followed by detection of ion charge states after illumination with delayed 400 nm laser pulses. A timing jitter of the order of several hundred femtoseconds between laser- and accelerator-pulses was compensated for by a simultaneous delay measurement in a single-shot x-ray/laser cross-correlator. After sorting of the tagged spectra according to the measured delays, a temporal resolution equivalent to the pulse duration of the optical laser could be established. While results on ion charge states up to Xe(4+) are compatible with a previous study using a high-harmonic soft x-ray source, a new relaxation pathway is opened by the nonlinear excitation of xenon atoms in the intense free-electron laser light field, leading to the formation of Xe(5+).