X-ray scattering is a weak linear probe of matter. It is primarily sensitive to the position of electrons and their momentum distribution. Elastic X-ray scattering forms the basis of atomic structural determination while inelastic Compton scattering is often used as a spectroscopic probe of both single-particle excitations and collective modes. X-ray free-electron lasers (XFELs) are unique tools for studying matter on its natural time and length scales due to their bright and coherent ultrashort pulses. However, in the focus of an XFEL the assumption of a weak linear probe breaks down, and nonlinear light-matter interactions can become ubiquitous. The field can be sufficiently high that even non-resonant multiphoton interactions at hard X-rays wavelengths become relevant. Here we report the observation of one of the most fundamental nonlinear X-ray-matter interactions, the simultaneous Compton scattering of two identical photons producing a single photon at nearly twice the photon energy. We measure scattered photons with an energy near 18 keV generated from solid beryllium irradiated by 8.8-9.75 keV XFEL pulses. The intensity in the X-ray focus reaches up to 4x20 W/cm2, which corresponds to a peak electric field two orders of magnitude higher than the atomic unit of field-strength and within four orders of magnitude of the quantum electrodynamic critical field. The observed signal scales quadratically in intensity and is emitted into a non-dipolar pattern, consistent with the simultaneous two-photon scattering from free electrons. However, the energy of the generated photons shows an anomalously large redshift only present at high intensities. This indicates that the instantaneous high-intensity scattering effectively interacts with a different electron momentum distribution than linear Compton scattering, with implications for the study of atomic-scale structure and dynamics of matter