It has been assumed that categories are coherent, because they reflect feature correlations in the world, because the human conceptual system is designed to create systematic categories, and because people have theories about the world that lend coherence to sets of features that may seem unrelated on the surface. In this paper, we suggest that the need to establish referential communication also influences category coherence. In order to begin to forge the link between referential communication and categorization, we present two studies involving a referential communication task in which people build LEGO models collaboriatively. These studies suggest that communication promotes consistency between individuals, which helps to synchronize the category structures of different people. In addition, these studies demonstrate that communication focuses people on the commonalities of objects as well as on the differences related to the commonalities--a pattern that is compatible with what has been observed with existing categories. Finally, referential expressions developed in this task can be applied productively to new objects, allowing the labels to be generalized beyond the set of items for which they were established initially. These results suggest that referential communication is an important determinant of the structure of category representations, and that categorization research must incorporate communication tasks into the canon of methodologies used to study category structure.