The rise of social media has spawned private news organizations in China that are encountering problems regarding how to gain public and journalistic acceptance and recognition as newcomers and how to survive without a news license. Drawing on organizational legitimacy theory, this paper investigates the strategies employed by private news organizations to construct multiple layers of legitimacy including regulatory, normative and cognitive legitimacy in China's unique context and the social media era. Based on in-depth interviews with 20 practitioners of private news organizations and participant observation in one private news agency, findings showed that private news organizations (1) gain regulatory legitimacy through news production methods including “misplacing registration”, “playing with official hats” and “depoliticization”; (2) establish normative legitimacy by emphasizing their adherence to traditional journalistic values, norms, and routines, and their similarities to state-owned media; (3) obtain cognitive legitimacy through the creation of “hot news” with reliance on professional reputation. This study thereby explores these strategies to reflect the path of “dependent autonomy” of private news organizations and provides an institutional and organizational perspective to understand the constraints and characteristics of social media journalism in China.