This article explores direct and indirect antecedents that contribute to corporate image formation in a service recovery context. Two studies were carried out in Egypt. Study 1 comprises 29 semistructured interviews with complainants of mobile phone network service providers in Egypt. Study 2 encompasses a mail survey of another 437 complainants. Findings reveal the importance of perceived justice, namely, interactional justice, in corporate image formation, as well as the mediating role of satisfaction with service recovery in the perceived justice-corporate image relationship. Results also reveal two empirical relationships: problem solving as a determinant of distributive justice and follow-up as a driver of procedural justice. Accordingly, this study contributes to the service field by providing the first empirical evaluation of new direct and indirect antecedents of corporate image formation in a service recovery context. Managerial recommendations are provided that encourage service practitioners to emphasize perceived justice and satisfaction with a service recovery process to enhance the company’s image. Additionally, companies should invest in implementing problem solving and follow-up as service recovery strategies since both significantly enhance perceived justice.