We report the discovery of HATS-71b, a transiting gas giant planet on a P=3.7955day orbit around a G=15.35mag 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 (TIC234523599). Combining all of these data, and utilizing Gaia DR2, we find that the planet has a radius of 1.024{+/-}0.018R_J_ and mass of 0.37{+/-}0.24M_J_ (95% confidence upper limit of <0.80M_J_), while the star has a mass of 0.4861{+/-}0.0060M_{sun}_ and a radius of 0.4783{+/-}0.0060R_{sun}_.