First-principles calculations were carried out to investigate the structure, phase stability, electronic property, and roles of metallicity in the hardness for recently synthesized FeB4 with various different structures. Our calculation indicates that the orthorhombic phase with Pnnm symmetry is the most energetically stable one. The other four new dynamically stable phases belong to space groups monoclinic C2/m, orthorhombic Pmmn, trigonal R (3) over barm, and hexagonal P6(3)/mmc. Their mechanical and thermodynamic stabilities are verified by calculating elastic constants, formation enthalpies, and phonon dispersions. We found that all phases are stabilized further under pressure. Above the pressure of about 50 GPa, the formation enthalpy of Pmmn is almost equal to that of P6(3)/mmc phase. The analysis on density of states not only demonstrates that formation of strong covalent bonding in these compounds contributes greatly to their stabilities but also that they all exhibit metallic behavior which does not relate to the approach used. By considering metallic contributions, the estimated Vickers hardness values based on the semiempirical model show that the OsB4-structured FeB4, with a hardness of 48.1 GPa, well exceeding the limitation of superhardness (40 GPa), is more hard than the most stable phase. The others are predicted to be potential hard materials. Moreover, the atomic configuration and strong B B covalent bonds are found to play important roles in the hardness of materials.