Two opposing accounts of early language evolution, the compositional and the holistic, have become the subject of lively debate. It has been argued that an evolving compositional protolanguage would not be useful for communication until it reached a certain level of grammatical complexity. This paper offers a new, discourse-oriented perspective on the debate. It argues that discourse should be viewed, not as a level of language structure ‘beyond the sentence’, but as sequenced communicative behaviour, typically but not uniquely involving language. This provides for continuity from exchanges making use of simple communicative resources such as single words and gestures to those making use of complex grammatical conventions. Supporting evidence comes from child language and from original experiments with adults using constrained language systems. The paper shows that the utility of emerging compositional language is not dependent on some critical level of complexity, and so defends the compositional account.