Discourse markers are verbal and nonverbal devices that mark transition points in communication. They presumably facilitate the construction of a mental representation of the events described by the discourse. A taxonomy of these relational markers is one important beginning in investigations of language use. Although several taxonomies of coherence relations have been proposed for monolog, only a few have been proposed for dialog. This article argues that discourse markers are important in language use because they operate at different levels of the dialog. What these levels are and how markers function is discussed by amalgamating 2 leading theories of language use. Based on this theory, a taxonomy of between-turn coherence relations in dialog is presented and several issues that arise out of constructing such a taxonomy are discussed. By sampling a large number of discourse markers from a corpus and substituting each marker for all other markers, this extensive substitution test could determine whether hyponymous, hypernymous, and synonymous relations existed between the markers from this corpus of dialogs. Evidence is presented for clustering this set of discourse markers into four categories: direction, polarity, acknowledgment, and emphatics.