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 studying the upper layers of atmospheres in this context. We report on the results from Hot Exoplanet Atmosphere Resolved with Transit Spectroscopy survey (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 High-Accuracy Radial-velocity Planet Searcher (HARPS) high-resolution spectrograph at the European Southern Observatory (ESO) 3.6 m telescope and collected 175 spectra of WASP-76. We repeatedly detect the absorption signature of neutral sodium in the planet atmosphere (0.371 ± 0.034%; 10.75σ in a 0.75 Å passband). The sodium lines have a Gaussian profile with full width at half maximum (FWHM) of 27.6 ± 2.8 km s⁻¹. This is significantly broader than the line spread function of HARPS (2.7 km s⁻¹). We surmise that the observed broadening could trace the super-rotation in the upper atmosphere of this ultra-hot gas giant.