There have been ample studies of the many phases of H2O in both its solid and low pressure liquid states, and the transitions between them. Using molecular dynamics simulations we address the hitherto unexplored deeply supercritical pressures, where no qualitative transitions are thought to take place and where all properties are expected to vary smoothly. On the basis of these simulations we predict that water at supercritical pressures undergoes a structural crossover across the Frenkel line at pressures as high as 45 times the critical pressure. This provides a new insight into the water phase diagram and establishes a link between the structural and dynamical properties of supercritical water. Specifically, the crossover is demonstrated by a sharp and pronounced at low pressures, and smooth at high pressures, signified by changes in the pair distribution functions and local coordination which coincide with the dynamical transition (the loss of all oscillatory molecular motion) at the Frenkel line on the phase diagram.