We report 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. Coherent X-ray pulsations around 527.4 Hz (1.9 ms) with a clear Doppler modulation were detected. This implies an orbital period of ∼8.8 h and a projected semi-major axis of ∼1.23 lt-s. With the binary mass function, we estimate a minimum companion mass of 0.42 M, obtained assuming a neutron star mass of 1.4 M and an inclination angle lower than 60°, as suggested by the absence of eclipses or dips in the light curve of the source. The broad-band energy spectrum, obtained by combining NuSTAR, swift and INTEGRAL observations, 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 that is compatible with an emission region of a few kilometers and a temperature compatible with the seed source of Comptonisation. A weak Gaussian line centred on the iron Kα complex can be interpreted as a signature of disc reflection. A similar spectrum characterises the NICER spectra, which was measured when the outburst faded.