Studies of monolingual speakers have shown a strong association between lexical learning and short-term memory (STM) capacity, especially STM for serial order information. At the same time, studies of bilingual speakers suggest that phonological knowledge is the main factor that drives lexical learning. This study tested these two hypotheses simultaneously in participants with variable levels of English–French bilingual proficiency. A word–nonword paired-associate learning task was administered, with nonwords obeying French phonotactic patterns. French phonological knowledge was estimated by a composite French proficiency score summarizing productive and receptive French vocabulary knowledge as well as quantitative and qualitative measures of French exposure. STM measures maximized retention of order information (serial order reconstruction) or retention of phonological item information (single nonword delayed repetition). The French proficiency score and the serial order STM measure independently predicted performance on the paired-associate learning task. These results highlight the conjoined role of phonological knowledge and serial order STM in lexical learning. Importantly, serial order STM remains a strong predictor of lexical learning, even for bilingual individuals who have broad phonological knowledge.