Experimental studies of compressed matter are now routinely conducted at pressures exceeding 1 mln atm (100 GPa) and occasionally at pressures greater than 10 mln atm (1 TPa). The structure and properties of solids that have been so significantly squeezed differ considerably from those of solids at ambient pressure (1 atm), often leading to new and unexpected physics. Chemical reactivity is also substantially altered in the extreme pressure regime. In this feature paper we describe how synergy between theory and experiment can pave the road towards new experimental discoveries. Because chemical rules-of-thumb established at 1 atm often fail to predict the structures of solids under high pressure, automated crystal structure prediction (CSP) methods are increasingly employed. After outlining the most important CSP techniques, we showcase a few examples from the recent literature that exemplify just how useful theory can be as an aid in the interpretation of experimental data, describe exciting theoretical predictions that are guiding experiment, and discuss when the computational methods that are currently routinely employed fail. Finally, we forecast important problems that will be targeted by theory as theoretical methods undergo rapid development, along with the simultaneous increase of computational power.