Tungsten tetraboride has been known so far as a non-stoichiometric compound with a variable composition (e.g. WB4-x, WB4+x). Its mechanical properties could exceed those of hard tungsten carbide, which is widely used nowadays in science and technology. The existence of stoichiometric WB4 has not been proven yet, and its structure and crystal chemistry remain debatable to date. Here we report the synthesis of single crystals of the stoichiometric WB4 phase under high-pressure high-temperature conditions. The crystal structure of WB4 was determined using synchrotron single-crystal X-ray diffraction. In situ high-pressure compressibility measurements show that the bulk modulus of WB4 is 238.6(2) GPa for B = 5.6(0). Measurements of mechanical properties of bulk polycrystalline sub-millimeter size samples under ambient conditions reveal a hardness of similar to 36 GPa, confirming that the material falls in the category of superhard materials.