In 2012, Bottoms and Tankebe put forward the notion that the legitimacy of criminal justice agencies is in flux and resembles an ongoing conversation between ‘power-holders’ and their ‘audience’. However, their dialogic approach has yet to be studied in empirical research in a policing and social media context. This paper provides an original contribution to their framework and illustrates the dynamic nature of police legitimacy on social media. Extensive fieldwork was carried out in Scotland and involved observation (n=134 hours) and semi-structured interviews (n=40) with police officers and civilian staff with social media duties, and focus groups with citizens (n=22). The research findings show that police legitimacy on social media is dynamic and has four key dimensions. Firstly, police officers and civilian staff cultivate their own sense of self-legitimacy on social media in accordance with the credibility of police information and their expertise in policing. Secondly, police officers and civilian staff communicate their legitimacy to citizens on social media drawing on formal and informal styles. Thirdly, citizens make assessments about police legitimacy on social media in connection to how they understand face-to-face encounters with the police, as the police themselves internalise these judgements. Fourthly, when citizens challenge police legitimacy on social media, officers and civilian staff reconstruct and at times reassert their legitimacy.