The structural and mechanical response of metals is intimately connected to phase transformations. For instance, the product of a phase transformation (martensite) is responsible for the extraordinary range of strength and toughness of steel, making it a versatile and important structural material. Although abundant in metals and alloys, the discovery of new phase transformations is not currently a common event and often requires a mix of experimentation, predictive computations, and luck. High-energy pulsed lasers enable the exploration of extreme pressures and temperatures, where such discoveries may lie. The formation of a hexagonal (omega) phase was observed in recovered monocrystalline body-centered cubic tantalum of four crystallographic orientations subjected to an extreme regime of pressure, temperature, and strain-rate. This was accomplished using high-energy pulsed lasers. The omega phase and twinning were identified by transmission electron microscopy at 70 GPa (determined by a corresponding VISAR experiment). It is proposed that the shear stresses generated by the uniaxial strain state of shock compression play an essential role in the transformation. Molecular dynamics simulations show the transformation of small nodules from body-centered cubic to a hexagonal close-packed structure under the same stress state (pressure and shear).