This paper proposes a coevolutionary scenario on the origins of compositionality and word order regularity in human language, and illustrates it using a multi-agent, behavioral model. The model traces a 'bottom-up' process of syntactic development; artificial agents, by iterating local orders among lexical items, gradually build up basic constituent word order(s) in sentences. These results show that structural features of language (e.g. syntactic categories and word orders) could have coevolved with lexical items, as a consequence of general learning mechanisms (e.g. pattern extraction and sequential learning) initially not language-specific. © John Benjamins Publishing Company.link_to_subscribed_fulltex