Studying the correlation between traits of interacting species has long been a popular approach for identifying putative cases of coevolution. More recently, such approaches have been used as a means to evaluate support for the geographic mosaic theory of coevolution. Here we examine the utility of these approaches, using mathematical and computational models to predict the correlation that evolves between traits of interacting species for a broad range of interaction types. Our results reveal that coevolution is neither a necessary nor a sufficient condition for the evolution of spatially correlated traits between two species. Specifically, our results show that coevolutionary selection fails to consistently generate statistically significant correlations and, conversely, that non-coevolutionary processes can readily cause statistically significant correlations to evolve. In addition, our results demonstrate that studies of trait correlations per se cannot be used as evidence either for or against a geographic mosaic process. Taken together, our results suggest that understanding the coevolutionary process in natural populations will require detailed mechanistic studies conducted in multiple populations or the use of more sophisticated statistical approaches that better use information contained in existing data sets.