We report the discovery of hysteresis between the x-ray spectrum and luminosity of black-hole binary LMC X-3. Our observations, with the Proportional Counter Array on the Rossi X-ray Timing Explorer, took place entirely within the soft spectral state, dominated by a spectral component that was fitted well with a multicolor disk blackbody. A power-law component was seen only during times when the luminosity of the disk blackbody was declining. The x-ray luminosity at these times was comparable to that seen in transient systems (x-ray novae) when they return to the hard state at the end of an outburst. Our observations may represent partial transitions to the hard state; complete transitions have been seen in this system by Wilms et al. (2001). If they are related to the soft-to-hard transition in transients, then they demonstrate that hysteresis effects can appear without a full state transition. We discuss these observations in the context of earlier observations of hysteresis within the hard state of binaries 1E 1740.7-2942 and GRS 1758-258 and in relation to published explanations of hysteresis in transients.