Controlling ultraviolet light at the nanoscale using optical Mie resonances holds great promise for a diverse set of applications, such as lithography, sterilization, and biospectroscopy. However, Mie resonances hosted by dielectric nanoantennas are difficult to realize at ultraviolet wavelengths due to the lack of both suitable materials and fabrication methods. Here, we systematically search for improved materials by computing the frequency dependent optical permittivity of 338 binary semiconductors and insulators from first principles, and evaluate their potential performance as high refractive index materials using Mie theory. Our analysis reveals several interesting candidate materials among which boron phosphide (BP) appears particularly promising. We then prepare BP nanoparticles and demonstrate that they support Mie resonances at visible and ultraviolet wavelengths using both far-field optical measurements and near-field electron energy-loss spectroscopy. We also present a laser reshaping method to realize spherical Mie-resonant BP nanoparticles. With a refractive index above 3 and low absorption losses, BP nanostructures advance Mie optics to the ultraviolet.