Transition metal borides (TMBs) are currently the subject of intensive interest
because of their superhard and ultra-incompressible features. Some TMBs are classified as
superhard materials mainly due to the presence of strong boron-boron covalent
bonding. To guide the experiment, employing density functional theory with evolutionary algorithm for crystal structure prediction, the high-pressure crystal structures of transition-metal tetraborides (TMB$_4$, TM = Fe, Ru, and Os) have been reported in this work. The ambient phases of all three materials exhibit metallic phases with space groups of Pnnm, P6$_3$/mmc and Pmmn for FeB$_4$, RuB$_4$ and OsB$_4$, respectively. At elevated pressure, FeB$_4$ and OsB$_4$ undergo transition to tetragonal phases with space group I4$_1$/acd and P4$_2$/nmc at pressure of 53.7 and 11.0 GPa, respectively. These high-pressure phases are semiconducting and they interestingly exhibit superhard character. Both dynamic and elastic stabilities are fully investigated to ensure the existence of the predicted phases. Electronic density of states is performed to clarify structure phase transitions and formation of the superhard phases. With the advantageous properties in these materials, they might potentially be the promising multifunctional materials for advanced applications such as cutting tools or wear-resistant coatings. Therefore, this finding should substantially induce further experimental investigation.