This paper presents an automatic music selection system based on runner's step frequency. Recent development of portable music players like iPod has increased the number of those who listen to music while exercising. However, few systems which connect exercises with music selection have been developed. We propose a system that automatically selects music suitable for user's running exercises. Although many parameters can be taken into account, as a first step we focus on runner's step frequency. This system selects music with tempo suitable for runner's step frequency and when runner's step frequency changes, it executes another music selection. The system consists of three modules: step frequency estimation, music selection, and music playing. In the first module, runner's step frequency is estimated from data derived from an acceleration sensor. In the second module, appropriate music is selected based on the estimated step frequency. In the third module, the selected music is played until runner's step frequency changes. In the experiment, subjects ran on a running machine at different paces listening to the music selected by the proposed system. Experimental results show that the system can estimate runner's SPM accurately and on the basis of the estimated SPM it can select music appropriate for users' exercises with more than 85.0% accuracy, and makes running exercises more pleasing.