Using density functional theory, we show that the long-believed transition-metal tetraborides (TB(4)) of tungsten and molybdenum are in fact triborides (TB(3)). This finding is supported by thermodynamic, mechanical, and phonon instabilities of TB(4), and it challenges the previously proposed origin of superhardness of these compounds and the predictability of the generally used hardness model. Theoretical calculations for the newly identified stable TB(3) structure correctly reproduce their structural and mechanical properties, as well as the experimental x-ray diffraction pattern. However, the relatively low shear moduli and strengths suggest that TB(3) cannot be intrinsically stronger than c-BN. The origin of the lattice instability of TB(3) under large shear strain that occurs at the atomic level during plastic deformation can be attributed to valence charge depletion between boron and metal atoms, which enables easy sliding of boron layers between the metal ones.