До Второй мировой войны в Мельбурне проживало всего несколько русских православных семейств. В 1949 году новыми иммигрантами был основан покровский приход. Своего храма в то время не было и для проведения служб приходилось арендовать различные помещения.
В 1954 году Покровский приход в Мельбурне, бывший к тому времени одним из крупнейших в епархии, приобрёл пустовавший храм в Коллингвуде в стиле неоготики. Община росла. В 1960-х годах основной зал был перестроен и расширен, но места всё равно не хватало. Было принято решение о строительстве нового храма. Процесс выбора места и покупки земли был непростым и долгим.
5 ноября 1989 года архиепископ Павел (Павлов) совершил закладку нового собора в сослужении всего духовенства штата Виктории. В закладном камне были помещены частичка мощей мученицы Великой княгини Елизаветы в запечатанном медно-латунном цилиндре. Это основано на древней христианской практике строительства церквей над могилами святых мучеников.
Подготовительная работа Строительного комитета выявила тот факт, что осилить такой проект приход сможет только, если постройка будет осуществлена в основном своими руками. Выбранный в 1988 году староста Иннокентий Павлович Козулин возглавил рабочую артель добровольцев, большинство из которых имело опыт в строительстве. По словам протоиерея Николая Карыпова все бетонные, плотницкие, сварочные и штукатурные работы были сделаны руками добровольцев. Для работ по дереву были приглашены резчики из России. Они выполнили иконостас и другие киоты. Используя современные технологии, строители старались исполнить храм в Ярославском стиле XVI – XVII веков.
Двенадцать лет велись наружные работы, и семь лет ушло на создание внутреннего убранства храма. В феврале 1996 года были установлены позолоченные купола, которые были увенчаны крестами в октябре того же года. Строительство собора было закончено в начале 2000-х годов. За 2005 – 2006 годы был закончен зал, бетонная стоянка и дорожки вокруг храма. Начались работы по ландшафту и посадке травы и деревьев. 24 сентября 2006 года архиепископ Иларион (Капрал) совершил великое освящение нового Покровского собора.
