Abstract: Single crystals of novel orthorhombic (space group Pnnm) iron tetraboride FeB4 were synthesized at pressures above 8 GPa and high temperatures. Magnetic susceptibility and heat capacity measurements demonstrate bulk superconductivity below 2.9 K. The putative isotope effect on the superconducting critical temperature and the analysis of specific heat data indicate that the superconductivity in FeB4 is likely phonon mediated, which is rare for Fe-based superconductors. The discovered iron tetraboride is highly incompressible and has the nanoindentation hardness of 62(5) GPa; thus, it opens a new class of highly desirable materials combining advanced mechanical properties and superconductivity.