Tungsten borides are a unique class of compounds with excellent mechanical properties comparable to those of traditional superhard materials. However, the in-depth understanding of these compounds is hindered by the uncertainty of their phase relations and complex crystal structures. Here, we explored the W-B system systematically by ab initio variable-composition evolutionary simulations at pressures from 0 to 40 GPa. Our calculations successfully found all known stable compounds and discovered two novel stable phases, P4[combining macron]21m-WB and P21/m-W2B3, and three nearly stable phases, R3m-W2B5, Ama2-W6B5, and Pmmn-WB5, at ambient pressure and zero Kelvin. Interestingly, P4[combining macron]21m-WB is much harder than the known α and β phases, while Pmmn-WB5 exhibits the highest hardness. Furthermore, it is revealed that the much debated WB4 becomes stable as the P63/mmc (2 f.u. per unit cell) phase at pressures above ∼1 GPa, not at ambient pressure as reported previously. Our findings provide important insights for understanding the rich and complex crystal structures of tungsten borides, and indicate WB2, WB4, and WB5 as compounds with the most interesting mechanical properties.