This paper describes how a variation of card sorting- ‘repeated single-criterion sorting’, can be applied to the information architecture design of digital music services. 52 respondents were asked to sort, using their own choice of criteria, 12 popular songs using an online card sorting tool. Once respondents had chosen a construct for a particular sort, e.g. “Genre”, they placed each card into a named category, e.g. “Rock”, “Pop”, and were encouraged to repeat this process until they could think of no more constructs. High levels of agreement were found for a small number of constructs such as “genre”, “gender”, and “speed of song” but the remaining constructs were individual to each respondent, e.g. “songs that make me cry”. The results highlighted differences with current approaches to music categorisation, as well as the potential for repeated single-criterion sorting to be used to design faceted navigation structures.