A definitive determination of crystal structures is an important prerequisite for designing and exploiting new functional materials. Even though tungsten and molybdenum borides (TMBx) are the prototype for transition-metal light-element compounds with multiple functionalities, their elusive crystal structures have puzzled scientists for decades. Here, we discover that the long-assumed TMB2 phases with the simple hP3 structure (hP3-TMB2) are in fact a family of complex TMB3 polytypes with a nanoscale ordering along the axial direction. Compared with the energetically unfavorable and dynamically unstable hP3-TMB2 phase, the energetically more favorable and dynamically stable TMB3 polytypes explain the experimental structural parameters, mechanical properties, and X-ray diffraction (XRD) patterns better. We demonstrate that such a structural and compositional modification from the hP3-TMB2 phases to the TMB3 polytypes originates from the relief of the strong antibonding interaction between d electrons by removing one third of metal atoms systematically. These results resolve the longstanding structural mystery of this class of metal borides and uncover a hidden family of polytypic structures. Moreover, these polytypic structures provide an additional hardening mechanism by forming nanoscale interlocks that may strongly hinder the interlayer sliding movements, which promises to open a new avenue towards designing novel superhard nanocomposite materials by exploiting the coexistence of various polytypes.