The photoionization of heavy atoms, krypton and xenon, by ultra-intense X-ray laser pulses was studied at the novel X-ray free-electron laser (FEL), the Linac Coherent Light Source (LCLS). Using an ion time-of-flight (TOF) spectrometer, the ion charge-state distributions were retrieved at 1.5 and 2 keV photon energies as a function of the FEL pulse energy, while large X-ray pnCCD detectors simultaneously recorded the fluorescence spectra. The experimental findings are compared to calculations by S.-K. Son and R. Santra, that are based on perturbation theory and numerically solve a large number of coupled rate equations, and to photoionization processes in light atoms observed in previous measurements at LCLS. For xenon unprecedentedly high charge states, up to Xe36+, are found at 1.5 keV photon energy, 80 fs pulse length and 2.5 mJ pulse energy, although the ground-state ionization energy exceeds the photon energy starting at Xe26+ already. As direct multi-photon ionization was demonstrated to play a minor role at X-ray energies, a different ionization pathway has to be considered here. Measured fluorescence spectra along with the theoretical analysisindicate that ionization beyond the Xe26+ threshold is enabled by densely spaced excitation resonances which can be hit within a single broadband FEL pulse for several subsequent high charge states generated during the ionization process. In contrast to the 1.5 keV case, photoionization at 2 keV photon energy only proceeds up to Xe32+, because at higher photon energy accessible resonances appear at higher charge states, which are not reached within a single shot for the pulse energies used in the present experiment. In order to demonstrate the general nature of the multiple ionization mechanism involving resonances, similar measurements were performed for krypton at 2 keV. Here, combined experimental and theoretical analysis shows that, similar to the case of xenon at 1.5 keV, the highest observed charge state, Kr21+, can only be explained by the resonance-enhanced X-ray multi-ionization process. Based on the experimental data for two exemplary elements and the general model suggested to explain the results, resonance-enhanced photoionization in intense X-ray pulses is predicted to be a general phenomenon for heavy atoms. Thus, systems containing heavy atoms with large nuclear charge Z will experience dramatically increased photoionization in certain photon energy ranges, which can either be desirable, e.g. for the efficient creation of dense plasmas of high-Z atoms, or disturbing, e.g. for coherent diffractive imaging, where local radiation damage in the vicinity of heavy atoms can be significantly enhanced.