The learnability of center-embedded recursive structures has attracted much attention. However, previous studies adopted the artificial grammar learning paradigm and did not apply natural language stimuli. Accordingly, we attempt to tighten the link between artificial language learning and natural language acquisition in the auditory modality, by enriching our learning environment with phonological cues that occur in natural language, namely, spoken information, in particular, Chinese tones. In a grammaticality judgment task, we examined the syntactical processing by participants from different language backgrounds. Through the cross-language comparison between Chinese and Dutch native speakers, we aim to test the influence of language-specific phonological cues on processing complex linguistic structures. The results showed that tones had a more beneficial learning effect on Chinese than on Dutch participants. When participants learned a new language, they were likely to bring their own language routines implicitly from the familiar native language into processing the unfamiliar one.