Summary: We propose a novel paradigm that we named “Structural Hidden Markov Model” (SHMM). It extends traditional Hidden Markov Models (HMMs) by considering observations as strings derived by a probabilistic context-free grammar. These observations are related in the sense they all contribute to produce a particular structure. SHMMs overcome the limit of state conditional independence of the observations in HMMs. Thus they are capable to cope with structural time series data. We have applied SHMM to data mine customers’ preferences for automotive designs. A 5-fold cross-validation has shown a 9% increase of SHMM accuracy over HMM.