Current x-ray free electron lasers (FEL) can produce focused beams with peak electric field easily exceeding an atomic unit in strength and only four orders of magnitude below the QED critical field.    Under such conditions x-ray-matter interactions become nonlinear,  usually dominated by sequential processes. Here we present the observation of coherent nonsequential processes at hard x-ray energies including:  phase-matched second harmonic generation in diamond and two-photon Compton scattering in beryllium.  The former can be described in terms of a free-electron like nonlinearity, however, we find that this approximation breaks down spectacularly in the latter.  We discuss potential implications for the study of atomic-scale structure and dynamics of matter on FELs.