We introduce MySong, a system that automatically chooses chords to accompany a vocal melody. A user with no musical experience can create a song with instrumental accompaniment just by singing into a microphone, and can experiment with different styles and chord patterns using interactions designed to be intuitive to non-musicians. We describe the implementation of MySong, which trains a Hidden Markov Model using a music database and uses that model to select chords for new melodies. Model parameters are exposed to the user via intuitive interactors. We present results from a study demonstrating that chords assigned to melodies using MySong and chords assigned manually by musicians receive similar subjective quality ratings. We present results from a second study showing that 13 users with no background in music theory are able to create musical accompaniments in 10 minutes using our system, and that these accompaniments are rated positively by independent evaluators.