Stress relaxation upon cessation of shear flow is known to be described by single-mode or multimode monotonic exponential decays. This is considered to be ubiquitous in nature. However, we found that, in some cases, the relaxation becomes anomalous in that an increase in the relaxing stress is observed. Those observations were made for physicochemically very different systems, having in common, however, the presence of self-associating units generating structures at large length scales. The nonmonotonic stress relaxation can be described phenomenologically by a generic model based on a redistribution of energy after the flow has stopped. When broken bonds are reestablished after flow cessation, the released energy is partly used to locally increase the elastic energy by the formation of deformed domains. If shear has induced order such that these elastic domains are partly aligned, the reestablishing of bonds gives rise to an increase of the overall stress.