We introduce a new Markov Chain called the Cycle Walk for sampling measures of graph partitions where the partition elements have roughly equal size. Such Markov Chains are of current interest in the generation and evaluation of political districts. We present numerical evidence that this chain can efficiently sample target distributions that have been difficult for existing sampling Markov chains.