Incorporating bismuth, the heaviest element stable to radioactive decay, into new materials enables the creation of emergent properties such as permanent magnetism, superconductivity, and nontrivial topology. Understanding the factors that drive Bi reactivity is critical for the realization of these properties. Using pressure as a tunable synthetic vector, we can access unexplored regions of phase space to foster reactivity between elements that do not react under ambient conditions. Furthermore, combining computational and experimental methods for materials discovery at high-pressures provides broader insight into the thermodynamic landscape than can be achieved through experiment alone, informing our understanding of the dominant chemical factors governing structure formation. Herein, we report our combined computational and experimental exploration of the Mo-Bi system, for which no binary intermetallic structures were previously known. Using the ab initio random structure searching (AIRSS) approach, we identified multiple synthetic targets between 0-50 GPa. High-pressure in situ powder X-ray diffraction experiments performed in diamond anvil cells confirmed that Mo-Bi mixtures exhibit rich chemistry upon the application of pressure, including experimental realization of the computationally predicted CuAl2-type MoBi2 structure at 35.8(5) GPa. Electronic structure and phonon dispersion calculations on MoBi2 revealed a correlation between valence electron count and bonding in high-pressure transition metal-Bi structures as well as identified two dynamically stable ambient pressure polymorphs. Our study demonstrates the power of the combined computational-experimental approach in capturing high-pressure reactivity for efficient materials discovery.