Learning syntax requires determining relations between 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 found that the language could be acquired through cross-situational statistical correspondences with complex scenes and without explicit feedback, and that knowledge was maintained after 24 hours. Results also showed that verbs and word order were the first to be acquired, followed by nouns, adjectives and finally case markers. Interdependencies in learning were found for word order and verbs, and also for nouns, adjectives and case markers. Grammar and vocabulary can be acquired simultaneously, but with distinctive patterns of acquisition - grammar and the role of verbs first, then the vocabulary of other lexical categories.