Strategic management in the public sector has become quite popular in practice and several studies have shown that it has an impact on organizational performance. However, we still know little of how strategic management unfolds in practice. Overall, our message is that there are specific challenges that appear when applying strategic management in a public sector context that need to be handled to enhance the possibility of succeeding with strategy work. We present these challenges in terms of four tensions emerging in strategy work: planned versus emergent strategies, legitimacy versus practicality, administrative management versus innovative approach, and accessibility versus security. Based on these identified tensions, we suggest four propositions that not only have implications for further research, but also practical implications.