In music, chords are organized into hierarchical structures on the basis of musical syntax and the syntax of Western music can be implicitly acquired by listeners growing up in a Western musical culture. Here, we investigated whether Western musical syntax of different complexities can be implicitly acquired by non-native listeners growing up in China. This study used electroencephalography (EEG) to measure how the neural responses to musical sequences that either follow a simple rule, i.e., finite state grammar (FSG), or a complex rule, i.e., phrase structure grammar (PSG), are affected. We tested three groups of Chinese listeners who varied in their proficiency and experience in Western music. Only the high-proficiency group had received formal Western musical training, whereas the low- and moderate-proficiency groups varied in their degree of exposure to Western music. The results showed that in the FSG condition, the event-related potentials (ERPs) evoked by regular and irregular final chords were not significantly different in the low-proficiency group. In contrast, in the moderate- and high-proficiency groups, the irregular final chords evoked an ERAN-N5 biphasic response. In the PSG condition, however, only the high-proficiency group showed an ERAN-N5 biphasic response evoked by irregular final chords. This study provides evidence that although simple structures of Western music, such as FSG, can be acquired by long-term implicit learning, the acquisition of more complex structures, such as PSG, merely from exposure to western music may not be as easy.