Providing behavioural support to all students is increasingly recognised as an integral part of teaching and learning in schools throughout the world. This small-scale, qualitative study reports on the perceived challenges faced by staff in implementing school-wide behavioural support at two remote Indigenous primary schools in Queensland, Australia. Individual semi-structured interviews held with two administrators and six teachers revealed implementation barriers to be clustered around four themes: staff turnover and leadership change; staff training; consistency in teaching and responding to student behaviour; and involvement of parents and remote community. These initial findings highlight the need to extend investigations into barriers associated with implementing and sustaining this behavioural approach in other remote schools throughout Australia, as student behaviour influences student learning, and lifting educational outcomes for Indigenous students is a national priority.