Large language models demonstrate exceptional capabilities but raise critical safety concerns due to toxic outputs causing potential harm to users. Prompt optimization has emerged as a practical detoxification solution because it operates at the input level and can be applied to black-box or API-based models without parameter access. However, existing methods treat each task in a stateless manner without leveraging prior optimization experiences, which results in either ineffective detoxification or over-sanitized prompts that lose original intent in the vast search space. To address this, we propose the Memory-INformed Detoxification (MIND) framework that harnesses historical optimization experiences to enhance detoxification effectiveness through Memory Retrieval (MR) for retrieving relevant past cases and Memory Maintenance (MM) for maintaining a representative memory pool. We formulate MR and MM as optimization problems, prove their NP-hardness, and develop two approximation algorithms with constant approximation ratios for these problems. Experiments across multiple datasets and model configurations show that MIND outperforms existing baselines in both toxicity reduction and response utility.