Prompt optimization for Large Language Models (LLMs) has recently made great strides in complex tasks such as solving arithmetic problems and reasoning. Yet, its efficacy remains limited in tasks demanding extensive domain expertise beyond the internal knowledge of LLMs. As context length increases, prompt optimization tends to plateau in performance, which limits the amount of domain knowledge we can provide in the prompt. We postulate that this difficulty stems from an inherent tradeoff between adding information and easing comprehension. To tackle this challenge, we present a divide-and-conquer approach (RAPO) to prompt optimization by means of retrieval augmentation. RAPO breaks the entire problem space into a number of subspaces, where each subspace can be handled separately by a local prompt specifically designed to cater to it. This approach not only scales more effectively to larger training datasets but also naturally accommodates domain knowledge (e.g., policy databases) and inference algorithms (e.g., re-ranking). Experimental results show that RAPO consistently outperforms recent methods (Yang et al., 2023; Pryzant et al., 2023) by a large margin across challenging datasets, including, a 7.4% relative AUCPR improvement on internal datasets by incorporating domain knowledge and 13.0% relative AUCPR gain on the public Sarcasm dataset (Abu Farha & Magdy, 2020). We hope our findings offer a new perspective of prompt optimization for knowledge-intensive tasks.