DescriptionWe develop an Evolutionary Markov Chain Monte Carlo (EMCMC) algorithm for sampling from large multi-modal state spaces. Our algorithm combines the advantages of evolutionary algorithms (EAs) as optimization heuristics and the theoretical convergence properties of Markov Chain Monte Carlo (MCMC) algorithms for sampling from unknown distributions. We harness massive computational power with a parallel EA framework that guides a large set of Markov chains. Our algorithm has applications in many different fields of science. We demonstrate its effectiveness with an application to political redistricting.