The synthesis of materials in high-pressure experiments has recently attracted increasing attention, especially since the discovery of record breaking superconducting temperatures in the sulfur-hydrogen and other hydrogen-rich systems. Commonly, the initial precursor in a high pressure experiment contains constituent elements that are known to form compounds at ambient conditions, however the discovery of high-pressure phases in systems immiscible under ambient conditions poses an additional materials design challenge. We performed an extensive multi component $ab,initio$ structural search in the immiscible Fe--Bi system at high pressure and report on the surprising discovery of two stable compounds at pressures above $approx36$ GPa, FeBi$_2$ and FeBi$_3$. According to our predictions, FeBi$_2$ is a metal at the border of magnetism with a conventional electron-phonon mediated superconducting transition temperature of $T_{rm c}=1.3$ K at 40 GPa. In analogy to other iron-based materials, FeBi$_2$ is possibly a non-conventional superconductor with a real $T_{rm c}$ significantly exceeding the values obtained within Bardeen-Cooper-Schrieffer (BCS) theory.