Learning language requires acquiring the grammatical categories of words in the language, but learning those categories requires understanding the role of words in the syntax. In this study, we examined how this chicken and egg problem is resolved by learners of an artificial language comprising nouns, verbs, adjectives and case markers following syntactic rules. We also measured individual differences in declarative and procedural memory processing, which have been linked to vocabulary and grammar learning, respectively. The results showed that grammar and vocabulary can be acquired simultaneously, but with distinctive patterns of acquisition – the syntactic role of verbs and their referents first, then other lexical categories, and finally the syntactic function of case markers. Interdependencies in learning were found for word order and verbs, which related to verbal declarative memory, and also for nouns, adjectives and case markers, which related to procedural memory.