MESS (Mass-loss of Evolved StarS) is a Guaranteed Time Key Program that uses the PACS and SPIRE instruments on board the Herschel Space Observatory to observe a representative sample of evolved stars, that include asymptotic giant branch (AGB) and post-AGB stars, planetary nebulae and red supergiants, as well as luminous blue variables, Wolf-Rayet stars and supernova remnants. In total, of order 150 objects are observed in imaging and about 50 objects in spectroscopy. This paper describes the target selection and target list, and the observing strategy. Key science projects are described, and illustrated using results obtained during Herschel's science demonstration phase. Aperture photometry is given for the 70 AGB and post-AGB stars observed up to October 17, 2010, which constitutes the largest single uniform database of far-IR and sub-mm fluxes for late-type stars. Comment: A&A accepted