Emerging academic commentary asks how people can be prepared for work and leadership under conditions of increasing complexity. It has been noted, however, that treatments of leadership in the management literature have been slow to engage with complexity thinking and also remain largely focused on executive and middle level leadership. This paper explores the implications of complexity thinking for front-line leadership work. It does that, firstly, by considering leadership questions implied by newer theoretical perspectives on complex practice and secondly, by revisiting earlier insights into complex work at street level. Lipsky’s (1980) exploration of street-level bureaucracy suggested that unresolvable paradoxes in public policy have always created significant dilemmas for front-line practitioners and leaders. Policing, education and welfare are prime examples of this space. Indeed, Perez (2011) suggests that operational police and their leaders face uniquely complex dilemmas. Thirdly, then, this paper references research undertaken with 50 serving police officers in Melbourne to focus on key issues for contemporary front-line leadership.