This presentation reports on the first results of a large-scale research programme that aims to define and circumscribe the construct of phraseological complexity and to theoretically and empirically demonstrate its relevance for second language theory (cf. Paquot, 2017). Within this broad agenda, the study has two main objectives. First, it investigates to what extent measures of phraseological complexity can be used to describe L2 performance at different proficiency levels in a corpus of linguistic term papers written by French EFL learners. Second, it compares measures of phraseological complexity with traditional measures of syntactic and lexical complexity. Variety and sophistication are postulated to be the first two dimensions of phraseological complexity, which is approached via relational co-occurrences, i.e. co-occurring words that appear in a specific structural or syntactic relation (e.g. adjective + noun, adverbial modifier + verb, verb + direct object).