The principalship in Australia and elsewhere has been the focus of considerable research in the past few decades. Less well researched have been those holding middle-level leadership and management positions in schools, such as deputy principals, heads of school and so on (Kaplan & Owings, 1999; NCSL, 2003). Recent work by Cranston, Tromans and Reugebrink (2004) suggested that those holding such middle-level leadership positions in schools, certainly in the state secondary sector, were struggling with what could be termed a reconceptualisation of their positions. One of the acknowledged limitations of this earlier study was that it was confined to state schools only, raising the question as to whether similar findings and struggles might be evident for those in non-state sectors of schooling in Australia. The research reported here is a first exploratory step in addressing this question as it reports data from middle-level school leaders in the non-state sector in Queensland and New South Wales. It suggests that many such leaders, like their counterparts in the state sector, are struggling with challenges to, and a reconceptualisation of, their roles. Of note, is that their potential leadership contribution to their schools is unrealised. Using an aircraft analogy, rather than working as co-pilots in their schools, they are actually working more like flight stewards. Recommendations for further research emerge from the findings.