It is known that one can characterize the decoherence strength of a Markovian environment by the product of its temperature and induced damping, and order the decoherence strength of multiple environments by this quantity. By deriving the non-Markovian dissipator of the completely-positive semi-group theorem for a general system with weak coupling to its environment, we show that for non-Markovian environments there also exists a natural (albeit partial) ordering of environment-induced irreversibility within a perturbative treatment. This measure can be applied to both low-temperature and non-equilibrium environments. (c) 2012 Elsevier B.V. All rights reserved.