Costelloe was born in Melbourne on 3 February 1954. Educated there at St Peter's East Bentleigh and Salesian College, Chadstone, he commenced teacher training at Christ College, Melbourne, before joining the Salesians of Don Bosco in 1977. He graduated from Christ College in 1978. Professed as a Salesian in 1985, Costelloe was ordained as a priest on 25 October 1986 by Archbishop Sir Frank Little in Melbourne.[1]
After three years at Salesian College, Chadstone, he was transferred to Rome where he completed a Licentiate in Sacred Theology at the Salesian Pontifical University in 1991. On his return to Melbourne, Costelloe began lecturing in theology at Catholic Theological College in Melbourne. Transferred to Perth in 1996, Costelloe served as parish priest St Joachim's Victoria Park and lectured at the University of Notre Dame Australia, Fremantle. He completed his doctorate in theology from the Melbourne College of Divinity. He returned to Melbourne in 1999, was appointed as rector to the Salesian community, and resumed teaching commitments at the Catholic Theological College. He was appointed as parish priest of St John the Baptist's Clifton Hill in 2006 and as parish priest of the adjoining St Joseph'sCollingwood in 2007. During this period he also held a number of senior positions in the Salesian order.[1]
With a strong interest in Catholic education, Costelloe held a number of senior roles in the Melbourne archdiocese, including being the episcopal vicar for tertiary education and the chair of the Catholic Education Commission of Victoria. An adjunct professor at the Australian Catholic University, he is also a member of the Australian Catholic Bishops Conference Commission for Catholic Education.[1]