Single crystals of novel orthorhombic (space group Pnnm) iron tetraboride FeB4 were synthesised at pressures above 8 GPa and high temperatures. Magnetic susceptibility measurements demonstrated bulk superconductivity below 2.9 K. The putative isotope effect on the superconducting critical temperature indicates that FeB4 is likely a phonon-mediated superconductor, which is unexpected in the light of previous knowledge on Fe-based superconductors. The discovered iron tetraboride is highly incompressible and has the nanoindentation hardness of 65(5) GPa, thus, it opens a new class of highly desirable materials combining advanced mechanical properties and superconductivity.