Word learning research has shown that learners constrain the hypothesis space for word meanings by using multiple sources of information, such as cross-situational regularities of word-context co-occurrences or syntactic cues like the number of arguments. These studies typically focus on word meaning development where these cues can be helpful but not necessary. As such, it sheds little light on the acquisition of anaphors, which requires tracking syntactic dependencies across situations. To test whether or how learners track this information, we conducted a novel anaphor learning experiment with English and Japanese speakers, manipulating cross-situational regularities in anaphors and their syntactic dependencies. Results show both English and Japanese speakers closely track the frequency of interpretive possibilities for novel anaphors. However, they demonstrate difficulties learning long-distance reflexives, which are compatible with either local or non-local antecedents. This suggests that successful anaphor learning requires more than cross-situational regularities of interpretive possibilities.