This paper investigates native speakers' awareness of non-adjacent phonological dependencies, specifically vowel harmony patterns and vowel pattern frequency in Khalkha Mongolian (Khalkha), and provides the first psycholinguistic work on Khalkha. In two experiments, this paper shows that not only is speakers' behavior affected by the form of non-adjacent phonotactic patterns, but also by their frequency. This is somewhat surprising as previous learnability studies on non-adjacent dependencies using artificial languages and pattern learning experiments have shown that subjects acquire these dependencies only with difficulty (e.g., Cleeremans & McClelland 1991; Gomez 2002; Newport & Aslin 2004; Finley & Badecker 2008). Although much native language work on phonotactic restrictions (e.g., Bailey & Hahn 2001) and phonological pattern frequency also exists, it has focused only on adjacent phonological patterns (e.g., Coleman & Pierrehumbert 1997; Frisch, Large & Pisoni 2000; Pierrehumbert 1994; Vitevitch, Luce, Charles-Luce & Kemmerer 1997). This paper explores this gap in the literature using native language data on non-adjacent dependencies. This research increases our understanding of the role of phonotactics in perception, as well as language-specific biases on cognition. Furthermore, it has implications for continued inquiries in production and perception, including formal theories of language, in particular theories which propose contiguity between vowels or vowel tiers within representations, as well as speech segmentation, lexical access, and lexical organization.