This chapter aims to enhance our understanding of the relation between public innovation and organizational legitimacy. On the basis of the literature, we formulate the expectation that top-down innovation results in strengthening of a bureaucratic logic to producing legitimacy whereas bottom-up innovation results in more emphasis on a network logic. To investigate this expectation empirically, the chapter analyses the introduction and use of social media by the Dutch police. The outcomes challenge the expected relation: top-down innovation resulted in a more networked arrangement for legitimacy. We explain this finding by pointing out that the innovation process was infrastructural and empty in content: the content was provided through bottom-up innovation. We conclude that combinations of top-down and bottom-up practices can form a conceptual lens for studying the involvement of different organizational actors in processes of public innovation.