The services marketing literature focuses on the measurement of service quality and its impact and consequences on businesses. This is important as service quality affects behavioural outcomes such as repeat purchases and loyalty. Research in this respect has been concentrated in the banking, financial, insurance and health care sectors. We examine how service quality can be effectively used as a basis for customer segmentation in the international airline industry, which is facing huge competition. Customers of a large international airline were segmented based on their travel behaviour, i.e. frequency, class, loyalty status and purpose of travel. Results of the segmentation analysis revealed that different groups of respondents perceived the service quality of the same airline differently. These results would allow international airlines to identify and have better access to its customers through the use of target marketing. The differences in perceptions of service quality between segments indicate that airlines today cannot apply a single service strategy to its entire customer base. To stay competitive they would need to consider more specific customer-focused strategies to meet the needs of the different identified market segments.