This study examines the relationships between perceived justice with service recovery (distributive, procedural, interactional, and informational), failure attributions (stability and controllability), recovery satisfaction, and loyalty. We collected data on perceived justice, failure attribution, recovery satisfaction, and customer loyalty through a survey of 263 airline passengers in Malaysia who experienced a service failure and subsequently a service recovery within the past year. The results reveal a significant relationship between perceived justice and recovery satisfaction in terms of distributive, procedural, and interactional justice. Recovery satisfaction had a significant effect on customer loyalty. The inclusion of failure attributions of stability and controllability as moderators indicates that both stability and controllability moderated the relationship between perceived justice and recovery satisfaction in terms of procedural, interactional, and informational justice, implying that the lower the stability and controllability of service failure, the stronger the positive relationship between procedural and informational justice and recovery satisfaction. These results have important implications for marketing theory and management.