Previous studies have indicated that dependencies between nonadjacent elements can be acquired by statistical learning when each element predicts only one other element (deterministic dependencies). The present study investigates statistical learning of probabilistic nonadjacent dependencies, in which each element predicts several other elements with a certain probability, as is more common in natural language. Three artificial language learning experiments compared statistical learning of deterministic and probabilistic nonadjacent dependencies. In Experiment 1, participants listened to sequences of three non-words containing either deterministic or probabilistic dependencies between the first and the last non-words. Participants exposed to deterministic dependencies subsequently distinguished correct sequences from sequences that violated the nonadjacent dependencies; participants exposed to probabilistic dependencies did not. However, when visual (Experiment 2) and phonological cues (Experiment 3) were added participants learned both kinds of dependencies, demonstrating statistical learning of probabilistic nonadjacent dependencies when additional cues are present. (Contains 1 table and 2 figures.)