The capacity to remember sequences is critical to many behaviors, such as navigation and communication. Adult humans readily recall the serial order of auditory items, and this ability is commonly understood to support, in part, the speech processing for language comprehension. Theories of short-term serial recall posit either use of absolute (hierarchically structured) or relative (associatively structured) position information. To date, neither of these classes of theories has been tested in a comparative auditory model. European starlings, a species of songbird, use temporally structured acoustic signals to communicate, and thus have the potential to serve as a model system for auditory working memory. Here, we explore the strategies that starlings use to detect the serial order of ecologically valid acoustic communication signals and the limits on their capacities to do so. Using a two-alternative choice operant procedure, we demonstrate that starlings can attend to the serial ordering of at least four song elements (motifs) and can use this information to classify differently ordered sequences of motifs. Removing absolute position cues from sequences while leaving relative position cues intact, causes recognition to fail. We then show that starlings can, however, recognize motif-sequences using only relative position cues, but only under rigid circumstances. The data are consistent with a strong learning bias against relative position information, and suggest that recognition of structured vocal signals in this species is inherently hierarchical. (Contains 2 tables and 7 figures.)