Русский православный собор святителя Николая Чудотворца был возведен в 1935 – 1936 годах. Это была первая специально построенная русская православная церковь в Австралии и один из более ранних приходов, основанных в русской диаспоре после 1917 года.
В связи с тем, что большое количество русских белых эмигрантов бежали из Советского Союза в этот период и обратились с просьбой эмигрировать в Австралию, правительство Квинсленда было вынуждено ослабить свои иммиграционные ограничения, которые были введены ранее. Наряду с этим наплывом белых русских эмигрантов в Брисбен в начале 1920-х годов был основан первый в городе православный приход России.
В 1925 – 1926 годах на месте нынешнего собора, приходом был приобретён дом и преобразован в церковь. В 1926 году отец Александр Шабашев был официально назначен настоятелем прихода. В 1930 году приход был зарегистрирован как Свято-Николаевская Русская Православная Церковь.
С назначением в 1933 году отца Валентина Антониева в приход Святого Николая, начался сбор средств на строительство новой церкви, которая должна была стать памятником последнему русскому царю Николаю II.
Инженер и местный прихожанин Григорий Мечоношин составил базовый план строительства новой церкви. Тендеры были объявлены в середине 1935 года, и контракт был передан строителю Б. Робинсону. Помощь в техническом строительстве купола оказал прихожанин Головзнин. Строительство началось в 1935 году, а в октябре 1936 года храм был освящен полным чином греческим православным архиепископом Тимофеем, поскольку в Австралии еще не был назначен русский православный епископ.
Русский православный собор Святого Николая остается неотъемлемой частью выживания русской культуры и религии в Брисбене. Богослужения проводятся на литургическом и церковно-славянском языках. Также каждые два месяца проводится англоязычная служба. В течение многих лет в церкви хранится важная библиотека русских произведений. Большая часть русской культурной самобытности в Брисбене остается связанной с традициями русского православия и Никольского собора.
