The trajectory of how organizations deal with stigma and legitimacy has been perceived as a monodirectional progression: stigma-overcoming followed by legitimacy-gaining. However, the iterative process where stigma and legitimacy could exist concurrently or take turns to influence the field, and the responses of organizations bearing such a dilemma have been insufficiently studied. To answer the question, I conducted a case study of the shadow education industry in China. Drawing on the institutional theory and following the grounded theory method, I examined two firms in this industry— New Oriental Education Group and Tomorrow Advancing Life Education Group. My findings propose a response model for organizations to handle the complexity in the environment, which includes two types of synchronous processes—legitimacy reinforcement process and stigma reduction process, and three orientations of institutional works—public-oriented alliance work, self-oriented evolution work, and future-oriented boundary work. By following this response model, organizations confronting institutional complexity can change the attitudes of different audiences, mitigate stigmatization present in the environment, make a progress, and prosper.