This paper describes a method for labelling structural parts of a musical piece. Existing methods for the analysis of piece structure often name the parts with musically meaningless tags, e.g., "p1", "p2", "p3". Given a sequence of these tags as an input, the proposed system assigns musically more meaningful labels to these; e.g., given the input "p1, p2, p3, p2, p3" the system might produce "intro, verse, chorus, verse, chorus". The label assignment is chosen by scoring the resulting label sequences with Markov models. Both traditional and variable-order Markov models are evaluated for the sequence modelling. Search over the label permutations is done with N-best variant of token passing algorithm. The proposed method is evaluated with leave-one-out cross-validations on two large manually annotated data sets of popular music. The results show that Markov models perform well in the desired task.