In 1989, Bp Gibran appointed the first committee of a new parish in Brisbane, which was registered in 1990. In 1993, Fr John Abdel-Karim became the first parish priest of the Church of St Paul, Woolloongabba, Brisbane.
In the mid-1990s, changing beliefs and practises in the Anglican Communion, culminating in the ordination of women to the priesthood, caused a number of clergy to leave the Anglican Communion and join the Orthodox Church. Many of these moved to the Antiochian Orthodox Church, creating St Barnabas Parish, Gold Coast; St Anthony the Great Parish, Perth; [[St. Anna's Monastery (Preston, Victoria)|St Anna's Monastery]], Melbourne; and a parish in Canberra (which later moved to [[Diocese of Australia and New Zealand|ROCOR]]), along with other clergy, including Fr Geoff Harvey, who were assigned to pre-existing churches.
Bishop Gibran reposed on 16 January 1999. Fr Elias Khoury was named as the temporary administrator of the diocese.