A first cobalt boride with the Co:B ratio below 1:1, Co5B16, was synthesized under high-pressure high-temperature conditions. It has a unique orthorhombic structure (space group Pmma, a = 19.1736(12), b = 2.9329(1), and c = 5.4886(2) {AA}, R1 (all data) = 0.037). The material is hard, paramagnetic, with a weak temperature dependence of magnetic susceptibility.