Using the PACS and SPIRE spectrometers on-board the Herschel Space Observatory, we obtained spectra of two red supergiants (RSGs) in the Large Magellanic Cloud (LMC). Multiple rotational CO emission lines (J=6-5 to 15-14) and 15 H2O lines were detected from IRAS 05280-6910, and one CO line was detected from WOH G64. This is the first time CO rotational lines have been detected from evolved stars in the LMC. Their CO line intensities are as strong as those of the Galactic RSG, VY CMa. Modelling the CO lines and the spectral energy distribution results in an estimated mass-loss rate for IRAS 05280-6910 of 3x10^-4 Msun per yr. The model assumes a gas-to-dust ratio and a CO-to-H2 abundance ratio is estimated from the Galactic values scaled by the LMC metallicity ([Fe/H]~-0.3), i.e., that the CO-to-dust ratio is constant for Galactic and LMC metallicities within the uncertainties of the model. The key factor determining the CO line intensities and the mass-loss rate found to be the stellar luminosity.