A large sub-mm survey with Herschel will enable many exciting science opportunities, especially in an era of wide-field optical and radio surveys and high resolution cosmic microwave background experiments. The Herschel-SPIRE Legacy Survey (HSLS), will lead to imaging data over 4000 sq. degrees at 250, 350, and 500 micron. Major Goals of HSLS are: (a) produce a catalog of 2.5 to 3 million galaxies down to 26, 27 and 33 mJy (50% completeness; 5 sigma confusion noise) at 250, 350 and 500 micron, respectively, in the southern hemisphere (3000 sq. degrees) and in an equatorial strip (1000 sq. degrees), areas which have extensive multi-wavelength coverage and are easily accessible from ALMA. Two thirds of the of the sources are expected to be at z > 1, one third at z > 2 and about a 1000 at z > 5. (b) Remove point source confusion in secondary anisotropy studies with Planck and ground-based CMB data. (c) Find at least 1200 strongly lensed bright sub-mm sources leading to a 2% test of general relativity. (d) Identify 200 proto-cluster regions at z of 2 and perform an unbiased study of the environmental dependence of star formation. (e) Perform an unbiased survey for star formation and dust at high Galactic latitude and make a census of debris disks and dust around AGB stars and white dwarfs.