We report the discovery by the HATSouth survey of HATS-4b, an extrasolar planet transiting a V = 13.46 mag G star. HATS-4b has a period of P ≈ 2.5167 days, mass of Mp ≈ 1.32 MJup, radius of Rp ≈ 1.02 RJup, and density of ρp = 1.55 ± 0.16 g cm-3 ≈ 1.24 ρJup. The host star has a mass of 1.00 M⊙, a radius of 0.92 R⊙, and a very high metallicity [Fe/H]=0.43 ± 0.08. HATS-4b is among the densest known planets with masses between 1 and 2 MJ and is thus likely to have a significant content of heavy elements of the order of 75 M⊕. In this paper we present the data reduction, radial velocity measurements, and stellar classification techniques adopted by the HATSouth survey for the CORALIE spectrograph. We also detail a technique for simultaneously estimating vsin i and macroturbulence using high resolution spectra.