Purpose – Data-driven market segmentation is heavily used by academic tourism and hospitality researchers to create knowledge and by data analysts in tourism industry to generate market insights. The stability of market segmentation solutions across repeated calculations is a key quality indicator of a segmentation solution. Yet, stability is typically ignored, risking that the segmentation solution arrived at is random. This study aims to offer an overview of market segmentation analysis and propose a new procedure to increase the stability of market segmentation solutions derived from binary data. Design/methodology/approach – The authors propose a new method – based on two independently proposed algorithms – to increase the stability of market segmentation solutions. They demonstrate the superior performance of the new method using empirical data. Findings – The proposed approach uses k-means as base algorithm and combines the variable selection method proposed by Brusco (2004) with the global stability analysis introduced by Dolnicar and Leisch (2010). This new approach increases the stability of segmentation solutions by simultaneously selecting variables and numbers of segments. Practical implications – The new approach can be adopted immediately by academic researchers and industry data analysts alike to improve the quality of market segmentation solutions derived from empirical tourist data. Higher quality market segmentation solutions translate into competitive advantage and increased business or destination performance. Originality/value – The proposed approach is newly developed in this study. It helps industry data analysts and academic researchers to reduce the risk of deriving random segmentation solutions by analyzing the data in a systematic way, then selecting the most stable solution using the segmentation variables contributing to this most stable solution only.