Tungsten borides are among a distinct class of transition-metal light-element compounds with superior mechanical properties that rival those of traditional superhard materials. An in-depth understanding of these compounds, however, has been impeded by uncertainties regarding their complex crystal structures. Here, we examine a wide range of chemical compositions of tungsten borides using a recently developed global structural optimization approach. We establish thermodynamically stable structures and identify a large number of metastable phases. These results clarify and correct previous structural assignments and predict new structures for possible synthesis. Our findings provide crucial insights for understanding the rich and complex crystal structures of tungsten borides, which have broad implications for further exploration of this class of promising materials.