We present analysis of more than 100 large-amplitude bipolar electrostatic structures in a quasi-perpendicular supercritical Earth's bow shock crossing, measured by the Magnetospheric Multiscale spacecraft. The occurrence of the bipolar structures is shown to be tightly correlated with magnetic field gradients in the shock transition region. The bipolar structures have negative electrostatic potentials and spatial scales of a few Debye lengths. The bipolar structures propagate highly oblique to the shock normal with velocities (in the plasma rest frame) of the order of the ion-acoustic velocity. We argue that the bipolar structures are ion phase space holes produced by the two-stream instability between incoming and reflected ions. This is the first identification of the ion two-stream instability in collisionless shocks.