We propose that listeners can use temporal regularities - spectro-temporal correlations that change smoothly over time - to discriminate animal vocalizations within and between species. To test this idea, we used Slow Feature Analysis (SFA) to find the most temporally regular components of vocalizations from birds (blue jay, house finch, American yellow warbler, and great blue heron), humans (English speakers), and rhesus macaques. We projected vocalizations into the learned feature space and tested intra-class (same speaker/species) and inter-class (different speakers/species) auditory discrimination by a trained classifier. We found that: 1) Vocalization discrimination was excellent (> 95%) in all cases; 2) Performance depended primarily on the ~10 most temporally regular features; 3) Most vocalizations are dominated by ~10 features with high temporal regularity; and 4) These regular features are highly correlated with the most predictable components of animal sounds.