Первые русские в Южной Австралии появились ещё до Первой мировой войны, но их было всего несколько человек. Массовое переселение русских, украинцев и белорусов началось в 1947 году.
В мае 1949 небольшая группа православных верующих в Аделаиде испросила благословения епископа Теодора для основания прихода в Аделаиде в честь Святого Николая. Поначалу прихожане встречались в доме Екатерины Игнатьевны Рубашкиной. Был выстроен иконостас. Но уже в начале 50-х годов стало ясно, что комната, отведенная для богослужений в доме Рубашкиной, не могла больше вмещать всех прихожан во время службы, и что пришло время подыскивать более просторное помещение.
С 1950 по 1957 приход снимал небольшой зал у Англиканской церкви на площади Витмор, но там были свои неудобства, т.к. часы, отведенные для службы были четко ограничены, иконостас необходимо было выносить после каждой службы. Были и другие неудобства. Прошло более 10 лет, и в ноябре 1955 года приход смог купить участок на нынешнем месте. Через год приход окончательно выплатил долг за землю и под руководством приходской строительно-технической группы (инженеры Н.М. Кованько и С.Ф. Циммерманн, архитекторы В.С. Пожидаев и А.В. Моквинская) построил зал, в котором разместилась временная церковь. Из наёмного зала был перенесён иконостас, который был немного изменён и поднят выше.
9 октября 1959 года на конкурсной основе был принят проект храма архитектора К.С. Рейсена в соавторстве В.С. Пожидаева, при участии инженера Н.М. Кованько. Проект был одобрен Епархиальным руководством, принят на Общем приходском собрании и разрешён городской властью к строительству в декабре 1960 года. Фундамент был залит после литургии, в воскресенье 30 августа 1961 года. Большая часть работ по постройке была выполнена силами прихожан. В течение многих лет продолжалась внутренняя роспись храма группой художников под руководством Антонины Бенедиктовны Ганиной.
Свято-Николаевский приход – многонациональный, объединяющий также представителей разных волн эмиграции