We demonstrate experimentally that a granular packing of glass spheres is capable of storing memory of multiple strain states in the dynamic process of stress relaxation. Modeling the system as a non-interacting population of relaxing elements, we find that the functional form of the predicted relaxation requires a quantitative correction which grows in severity with each additional memory and is suggestive of interactions between elements. Our findings have implications for the broad class of soft matter systems that display memory and anomalous relaxation.