Speakers are faster and more accurate at processing certain sound sequences within their language. Does this reflect the fact that these sequences are frequent or that they are phonetically less complex (e.g., easier to articulate)? It has been difficult to contrast these two factors given their high correlation in natural languages. In this study, participants were exposed to novel phonotactic constraints de-correlating complexity and frequency by subjecting the same phonological structure to varying degrees of probabilistic constraint. Participants' behavior was sensitive to variations in frequency, demonstrating that phonotactic probability influences speech production independent of phonetic complexity.