Existing research on how entrepreneurial storytelling is used to legitimate innovation and change has focused primarily on commercial settings. This paper extends analysis of entrepreneurial storytelling to a public institution, the U.S. federal government, and demonstrates how political context affects the stories told by institutional entrepreneurs seeking to legitimate radical change. Using qualitative historical archival methods, I content analyzed the use of and relationship between two co-existing institutional logics – the state logic and the market logic – embedded in 154 official stories in five annual reports (1993-1997) of the Clinton administration’s National Performance Review, popularly known as “Reinventing Government.” I found that the use of the state logic and the market logic in the administration’s stories changed over time and relative to each other. The stories initially emphasized an oppositional relationship between the two logics to justify the replacement of the state logic by the market logic as the dominant framework for guiding federal management. However, changes in the political context (i.e., Republican takeover of Congress in 1994) motivated the administration to construct stories that portrayed a collaborative relationship between the two logics, thus modifying its initial rhetoric of logic replacement by a subsequent rhetoric of logic hybridization. The study demonstrates that entrepreneurial storytelling by government actors constitutes an important rhetorical strategy through which the relationship between the central logics of two societal institutions, the state and the market, is politicized to create the enabling conditions for profound institutional transformation in the public sector.