We report the discovery of WASP-4b, a large transiting gas-giant planet with an orbital period of 1.34 days. This is the first planet to be discovered by the SuperWASP-South observatory and CORALIE collaboration and the first planet orbiting a star brighter than 16th magnitude to be discovered in the Southern hemisphere. A simultaneous fit to high-quality lightcurves and precision radial-velocity measurements leads to a planetary mass of 1.22 +/- 0.1 MJup and a planetary radius of 1.42 +/- 0.08 RJup. The host star is USNO-B1.0 0479-0948995, a G7V star of visual magnitude 12.5. As a result of the short orbital period, the predicted surface temperature of the planet is 1776 K, making it an ideal candidate for detections of the secondary eclipse at infrared wavelengths.