We present an accurate approach to compute X-ray photoelectron spectra based on the GW Green's function method that overcomes the shortcomings of common density functional theory approaches. GW has become a popular tool to compute valence excitations for a wide range of materials. However, core-level spectroscopy is thus far almost uncharted in GW. We show that single-shot perturbation calculations in the G0W0 approximation, which are routinely used for valence states, cannot be applied for core levels and suffer from an extreme, erroneous transfer of spectral weight to the satellite spectrum. The correct behavior can be restored by partial self-consistent GW schemes or by using hybrid functionals with almost 50% of exact exchange as a starting point for G0W0. We also include relativistic corrections and present a benchmark study for 65 molecular 1s excitations. Our absolute and relative GW core-level binding energies agree within 0.3 and 0.2 eV with experiment, respectively.