Individual differences in cognitive abilities and explicit instruction can affect language learning. Understanding how individual differences and instruction interact, however, requires us to determine the points in the language learning process that are open to influence. One hundred and eleven adults were exposed to an artificial language comprising transitive sentences occurring with action scenes and were either instructed or not in the language structure. Learning proceeded by determining the cross-situational correspondences between words and scene features. We found that declarative memory ability related strongly and positively but procedural memory related weakly and negatively to overall immediate learning. Rule-search instruction also positively influenced short-term learning, but not of the structure that was explicitly highlighted, and this was most pronounced in those with high declarative memory. The results highlight which features of language learning are accessible to information about language structure, and how that is affected by the learners’ cognitive abilities, with practical implications for personalised design of language learning programmes.