We report on the discovery by the Nuclear Spectroscopic Telescope Array (NuSTAR) and the Neutron Star Interior Composition Explorer (NICER) of the accreting millisecond X-ray pulsar IGR J17591-2342, detecting coherent X-ray pulsations around 527.4 Hz (1.9 ms) with a clear Doppler modulation. This implies an orbital period of ~8.8 hours and a projected semi-major axis of ~1.23 lt-s. From the binary mass function, we estimate a minimum companion mass of 0.42 solar masses, obtained assuming a neutron star mass of 1.4 solar masses and an inclination angle lower than 60 degrees, as suggested by the absence of eclipses or dips in the light-curve of the source. The broad-band energy spectrum is dominated by Comptonisation of soft thermal seed photons with a temperature of ~0.7 keV by electrons heated to 21 keV. We also detect black-body-like thermal direct emission compatible with an emission region of a few kilometers and temperature compatible with the seed source of Comptonisation. A weak Gaussian line centered on the iron K-alpha; complex can be interpreted as a signature of disc reflection. A similar spectrum characterises the NICER spectra, measured during the outburst fading.