We introduce Reprompting, an iterative sampling algorithm that searches for the Chain-of-Thought (CoT) recipes for a given task without human intervention. Through Gibbs sampling, we infer CoT recipes that work consistently well for a set of training samples. Our method iteratively samples new recipes by using previously sampled recipes as parent prompts to solve other training problems. Reprompting achieves consistently better performance than zero-shot, few-shot, human-written CoT prompting and strong automatic prompt optimization baselines on challenging reasoning benchmarks and brings up to +17 point improvements over the previous state-of-the-art method that uses human-written CoT prompts.