The aim of our work is to perform a market segmentation of the clients of Pousadas de Portugal, a network for over 40 high-end small hotels, ENATUR. The data for this work was provided by a sample of more than 2500 clients that filled in a given questionnaire. The segmentation is based on how often the clients used the hotels, and on the type of stay they were seeking. A few different techniques were used: mixed approaches using a-priori constitution of clusters and/or neural nets (SOM – Self-Organizing Maps) and/or k-means. Profiling the obtained segments adds some new insights about the clients and helps ENATUR managers to better support new marketing decisions.