Native language prosodic structure is known to modulate the processing of non-native suprasegmental information. It has been shown that native speakers of French, a language without lexical stress, have difficulties storing non-native stress contrasts. We investigated whether the ability to store lexical tone (as in Mandarin Chinese) also depends on the first language (L1) prosodic structure and, if so, how. We tested participants from a stress language (German), a language without word stress (French), a language with restricted lexical tonal contrasts (Japanese), and Mandarin Chinese controls. Furthermore, German has a rich intonational structure, while French and Japanese dispose of fewer utterance-level pitch contrasts. The participants learnt associations between disyllabic non-words (4 tonal contrasts) and objects and indicated whether picture--word pairs matched with what they had learnt (complete match, segmental or tonal mismatch conditions). In the tonal mismatch condition, the Mandarin Chinese controls had the highest sensitivity, followed by the German participants. The French and Japanese participants showed no sensitivity towards these tonal contrasts. Utterance-level prosody is hence better able to predict success in second language (L2) tone learning than word prosody.