Dissatisfied customers often use social media to voice their complaints effectively, and firms strive to find solutions about how to respond to publicly visible service failure posts. We add to the emerging literature on complaint handling via social media by examining how complaining customers on a company's Facebook page prefer to be treated. We built on the multi-attribute product concept and conducted four sequential studies in the air transport industry. Studies 1–3 were conducted to identify the service failures with a high magnitude of negative utilities as judged by consumers. The studies also served to build a service failure scenario involving relevant service recovery attributes related to the entire complaint process. The results showed that lost baggage had the highest magnitude of negative utility. The attributes that consumers found most appropriate in the case of lost baggage were timeliness and type of initial response, communication modes, compensation type, and types of information throughout the complaint process. Study 4 took this further by putting participants into the scenario to analyze their preferences, segments, and profiles. The findings presented in this study have practical implications for airlines and consumers because the results reveal four distinct consumer segments and indicate the presence of heterogeneous preferences for communication modes and interaction types across segments.