Two experiments examined sensitivity to key change in short sequences adapted from Bach chorales. In Experiment 1, musically trained listeners identified key changes in single-voice (i.e., soprano, alto, tenor, bass) and in four-voice presentations of the sequences. There were two main findings. First, listeners judged the distance and direction of key change in single voices and in four-voice harmony with approximately equal ease. Second, for four-voice harmony but not for single voices, the direction of key change on the cycle of fifths influenced perceived distance. For an equivalent number of steps on the cycle, greater distance was associated with modulations moving in the counterclockwise, rather than in the clockwise, direction. These findings were replicated in Experiment 2, in which musically untrained listeners rated perceived distance of key change. In addition, the directional asymmetry found for four-voice harmony also was found for individual bass voices. The evidence suggests that harmony and melody operate somewhat independently in the implication of key structure. Difficulties for a strictly hierarchical model of perceived musical pitch structure are discussed and a partially hierarchical model is considered.