An accurate description of the interaction of intense hard X-ray pulses with heavy atoms, which is crucial for many applications of free-electron lasers, represents a hitherto unresolved challenge for theory because of the enormous number of electronic configurations and relativistic effects, which need to be taken into account. Here we report results on multiple ionization of xenon atoms by ultra-intense (about 1019 W/cm2) femtosecond X-ray pulses at photon energies from 5.5 to 8.3 keV and present a theoretical model capable of reproducing the experimental data in the entire energy range. Our analysis shows that the interplay of resonant and relativistic effects results in strongly structured charge state distributions, which reflect resonant positions of relativistically shifted electronic levels of highly charged ions created during the X-ray pulse. The theoretical approach described here provides a basis for accurate modeling of radiation damage in hard X-ray imaging experiments on targets with high-Z constituents.