This article 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. 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 second language (L2) performance at different proficiency levels. 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). Phraseological diversity is operationalized as root type--token ratio computed for each syntactic relation. Two methods are tested to approach phraseological sophistication. First, sophisticated word combinations are defined as academic collocations that appear in the Academic Collocation List (Ackermann and Chen, 2013). Second, it is approximated with the average pointwise mutual information score as this measures has been shown to bring out word combinations made up of closely associated medium to low-frequency (i.e. advanced or sophisticated) words. The study reveals that unlike traditional measures of syntactic and lexical complexity, measures of phraseological sophistication can be used to describe L2 performance at the B2, C1 and C2 levels of the "Common European Framework of References for Languages" (CEFR), thus suggesting that essential aspects of language development from upper-intermediate to very advanced proficiency level may be situated in the phraseological dimension.