Probabilistic models have proved remarkably successful in modeling melodic organization (e.g., Huron, 2006a; Pearce, 2005; Temperley, 2008). However, the majority of these models rely on pitch information taken from melody alone. Given the prevalence of homophonic music in Western culture, however, surprisingly little attention has been directed at exploring the predictive power of harmonic accompaniment in models of melodic organization. The research presented here uses a combination of the three main approaches to empirical musicology—exploratory analysis, modeling, and hypothesis testing—to investigate the influence of harmony on melodic behavior. In this study a comparison is made between models that use only melodic information and models that consider the melodic information along with the underlying harmonic accompaniment to predict melodic continuations. A test of overall performance shows a significant improvement using a melodic-harmonic model. When individual scale degrees are examined, the major diatonic scale degrees are shown to have unique probability distributions for each of their most common harmonic settings. That is, the results suggest a robust effect of harmony on melodic organization. Perceptual implications and directions for future research are discussed.