In 1987 a group of Orthodox Christians in South Africa formed the
Society of St Nicholas of Japan to promote mission and evangelism among Orthodox Christians, and to make Orthodox Christianity better known and more welcoming to non-Orthodox people. The society invited Fr Chrysostom Frank, a priest who had served in South Africa before, to return as its chaplain, and formed a small worshipping community that used English in the Divine Liturgy. A couple of years later the community was strong enough to become a parish, independent of the society, and, after three years of worshipping in borrowed halls and chapels, bought an old Protestant church building in Brixton, Johannesburg, and converted it for Orthodox use. In 1996 Fr Chrysostom Frank left the Orthodox Church and joined the Roman Catholic Church. Clergy from neighbouring parishes helped with the celebration of the Divine Liturgy during 1997, while the parish was without a permanent priest. Fr Bert Olechnowicz came in December 1997, and returned to the USA at the beginning of 2002, and the [present priest is Fr Mircea Corpodean, from Romania.

The parish has recently started a daughter parish at Eldorado Park, south of Johannesburg, which is Afrikaans-speaking, and the priest there is Fr Jacobus van der Riet, who became Orthodox in St Nicholas Parish, and studied for the priesthood at St Tikhon's Theological Seminary in the USA.

The ikons on the ikonostasis were painted by a parishioner, Cathy McDonald, who also painted many of the ikons on the church walls. Other parishioners have also painted some of the ikons. The music in the services is mainly Slavonic, though with some hymns sung to Byantine and other melodies.