Two experiments investigated the structure of memory for titles of 54 familiar tunes. The titles were presented in the form of a hierarchy, with nodes labeled by genre (e.g., Rock or Patriotic). Four groups of subjects received logical or randomized titles, and logical or randomized labels. Goodness of label and title structure had equal and additive beneficial effects on recall with a 3-min exposure of the stimuli. With a 4-min exposure, good title structure became a larger contributor to good recall. Clustering analyses suggested that subjects were mentally representing the tune titles hierarchically, even when presentation was random.