Set within the broader employment crisis facing Australian schools, attracting preservice teachers to teach in a regional, rural, and remote (RRR) school community has been a long-standing educational priority. Research has identified the role of placement initiatives, the benefits of preparing preservice teachers for RRR contexts, and the centrality and significance of community and relationships. What is less frequently acknowledged is the role of school leaders in acting as the nexus between preservice teachers and the RRR community. Specifically, how leaders effectively support and enact relationship-based initiatives for preservice teachers. This research explores the leadership strategies of a group of high school leaders--leaders from a large metropolitan Prep-Year 12 College (Brisbane, Queensland) and Far North Queensland. Central to the leadership partnerships is a preservice teacher RRR preparation program facilitated by a Brisbane College via their Teacher Enhancement Centre. In this paper, we report on the strengths of their program in establishing key connections. Implications are drawn in relation to how school leaders connect with other leaders, and preservice teachers through the program, and how these connections can support place-based experiences for preservice teachers while concurrently addressing the staffing needs of RRR schools.