The national health insurance system in Australia records details on medical services and claims provided to its population. An effective method to the discovery of temporal behavioral patterns in the data set is proposed in this paper. The method consists of a two step approach which is applied recursively to the data set. First, a clustering algorithm is used to segment the data into classes. Then, hidden Markov models are employed to find the underlying temporal behavioral patterns. These steps are applied recursively to features extracted from the dataset until convergence. The main objective is to minimize the misclassification of patient profiles into various classes. This results in a hierarchical tree model consisting of a number of classes; each class groups similar patient temporal behavioral patterns together. The capabilities of the proposed method are demonstrated through the application to a subset of the Australian national health insurance data set. It is shown that the proposed method not only clusters data into various categories of interest, but it also automatically marks the periods in which similar temporal behavioral patterns occurred.