Evolutionary crystal structure prediction methods combined with density functional theory (DFT) calculations reveal a high-pressure (hp) phase of the intermetallic compound UCo crystalizing in the NaTl structure type ([Formula: see text]). We predict this compound to be formed at pressures below 9 GPa. Hp-UCo shows the same structural trends as the two experimentally known pseudo-binary compounds UCo0.2Rh0.8 and UNi0.8Pt0.2. We classify them as ordered solid solutions of a bcc lattice following Vegard's law. We predict hp-UCo and its adjacent phases UFe and UNi to be itinerant magnets. In the limit of vanishing spin-orbit interactions UFe and hp-UCo are half-metallic ferrimagnets. Spin-orbit coupling generally reduces the spin-polarization at the Fermi level. In case of hp-UCo the decrease depends on the applied DFT functional making the prediction of actual occurrence of half-metallicity problematic. In case of UFe the results are less dependent on the DFT functional. We demonstrate with these calulations that against 'common sense' also materials with heavy elements can be interesting candidates for half-metallicity. We highlight that the NaTl structure type should be an interesting candidate for further investigations of half-metallicity.