Musical knowledge, like native language knowledge, is largely implicit, being represented without awareness of its complex structures and incidentally acquired through interaction with a large number of samples. Two experiments explore implicit learning of hierarchical harmonic structures of different complexity employing an artificial grammar learning paradigm. The experiments consisted of an incidental learning phase using a distraction task, and a testing phase employing the process dissociation procedure paradigm (Jacoby, 1991). Participants performed significantly above chance and recognised adjacent and long-distance dependencies in both experiments. Confidence ratings and inclusion/exclusion response patterns suggest that both implicit structure knowledge and explicit judgment knowledge are in operation. Participants recognised stimuli with deep structures that appeared in the learning phase better than new structures for the more complex grammar, whereas there was no such difference for the simpler grammar. They performed significantly better for the less complex grammar which indicates that grammatical complexity affects learnability and recognition performance. The results conform to other experimental findings that musicians and nonmusicians are able to perceive long-distance dependencies and embedded structures in tonal harmony.