European starlings (Sturnus vulgaris) learned to discriminate patterns of 2000-Hz tones organized into rhythmic as compared with random, arrhythmic temporal structures, and the perceptual processes underlying the discrimination were then analyzed. Two rhythmic patterns were constructed, for different birds, according to a linear rule in which tones and intertone intervals of equal duration alternated or according to a hierarchical rule in which two subpatterns alternated. The arrhythmic pattern was a sequence of tone and intertone intervals each of random duration. The birds were required to peck at one key in the presence of a rhythmic pattern and at another key in the presence of the arrhythmic pattern to obtain food reward. All birds learned the rhythmic–arrhythmic discrimination, and discrimination accuracy was the same for both the linear and hierarchical rhythmic structures. In a series of transfer tests that followed, discrimination performance was tested when the temporal structure of the rhythmic stimulus patterns was transformed and when their pitch was shifted up or down an octave. For temporal transformations, performance was well maintained under (a) a log transformation which, from test to test, changed the absolute duration of tones and intertone intervals but kept their ratios constant (a simple tempo transformation); (b) an additive transformation which kept either tone duration or intertone interval constant from test to test while their counterparts changed in duration; and (c) a pattern interchange in which, for the appropriate birds, the linear was substituted for the hierarchical pattern, or the hierarchical was substituted for the linear pattern. Performance deteriorated (but remained above chance), however, when rhythmic patterns were degraded by holding tone (or intertone) duration constant while intertone (or tone) durations varied randomly within a test session. Performance was also well maintained when the baseline temporal patterns were shifted an octave in pitch, but the data do not necessarily force the conclusion that the birds showed true octave generalization. The results suggest the birds solved the rhythmic–arrhythmic discrimination on the basis of a nominal, qualitative pattern attribute, rhythmicity. Patterns are high in rhythmicity if pattern components are of constant duration within a test session, and if they reoccur periodically. Rhythmicity deteriorates as pattern components vary in duration within a test session and reoccur at varying time intervals. The results also show that the human capacity for discrimination among complex temporal patterns of sound is shared with at least one other species and may, therefore, represent a perceptual process that is—within limits yet to be determined—phylogenetically general.