We report the discovery of HATS-71b, a transiting gas giant planet on a day orbit around a mag M3 dwarf star. HATS-71 is the coolest M dwarf star known to host a hot Jupiter. The loss of light during transits is 4.7%, more than in any other confirmed transiting planet system. The planet was identified as a candidate by the ground-based HATSouth transit survey. It was confirmed using ground-based photometry, spectroscopy, and imaging, as well as space-based photometry from the NASA Transiting Exoplanet Survey Satellite mission (TIC 234523599). Combining all of these data, and utilizing Gaia DR2, we find that the planet has a radius of 1.024± 0.018 R J and mass of 0.37,± 0.24 M J (95% confidence upper limit of < 0.80 M J), while the star has a mass of 0.4861 pm 0.0060 M⊙ and a radius of 0.4783± 0.0060 R⊙.