High-resolution optical spectroscopy is a powerful tool to characterise exoplanetary atmospheres from the ground. The sodium D lines, with their large cross sections, are especially suited to study the upper layers of atmospheres in this context. We report on the results from HEARTS, a spectroscopic survey of exoplanet atmospheres, performing a comparative study of hot gas giants to determine the effects of stellar irradiation. In this second installation of the series, we highlight the detection of neutral sodium on the ultra-hot giant WASP-76b. We observed three transits of the planet using the HARPS high-resolution spectrograph at the ESO 3.6m telescope and collected 175 spectra of WASP-76. We repeatedly detect the absorption signature of neutral sodium in the planet atmosphere ($0.371pm0.034%$; $10.75 sigma$ in a $0.75$ r{A} passband). The sodium lines have a Gaussian profile with full width at half maximum (FWHM) of $27.6pm2.8$ km s$^{-1}$. This is significantly broader than the line spread function of HARPS ($2.7$ km s$^{-1}$). We surmise that the observed broadening could trace the super-rotation in the upper atmosphere of this ultra-hot gas giant.