Player’s physical experience is a critical factor to consider in designing motion-based games that are played through motion sensor gaming consoles or virtual reality devices. However, adjusting the physical challenge involved in a motion-based game is difficult and tedious, as it is typically done manually by level designers on a trial-and-error basis. In this paper, we propose a novel approach for automatically synthesizing levels for motion-based games that can achieve desired physical movement goals. By formulating the level design problem as a trans-dimensional optimization problem which is solved by a reversible-jump Markov chain Monte Carlo technique, we show that our approach can automatically synthesize a variety of game levels, each carrying the desired physical movement properties. To demonstrate the generality of our approach, we synthesize game levels for two different types of motion-based games and conduct auser study to validate the effectiveness of our approach.