October 19, 1890, the foundation stone for the original Church of St. Barnabas at the corner of Cook and Caledonia was laid, and the building was completed in a little under twelve weeks. In 1891, the church obtained the one-manual J.W. Walker organ which had come to Victoria in 1860 with the prefabricated "Iron Church", the original building of the Church of St. John the Divine.
August 6, 1912, a larger instrument of three manuals and 1,140 pipes arrived from England. It had been built by W. Denman of York about 1848 for a Wesleyan Chapel in Bridlington, Yorkshire, and had been reconditioned by Abbott and Smith of Leeds. Erection was completed in March of 1913. The Walker organ was sold to St. John the Baptist Anglican Church, Duncan BC, where it still serves, though in a rather battle-weary condition.
In 1948, a decision was made to erect a new building. November 16, 1952, the present building at the corner of Belmont and Begbie was consecrated by Archbishop Harold Sexton (1888-1972). The previous building, at the corner of Cook and Caledonia, became the home of the parish of St. Nicholas the Wonderworker, of the Ukrainian Catholic Eparchy of New Westminster.
Relocation of the old Denman organ to the new building was a lengthy volunteer effort led by Dr. David Longridge of the parish. It had been understood that the service life of this instrument was near its end, so at the annual meeting of the parish in 1955, Dr. Longridge advised bugetary provision for its replacement.
August 22, 1965, was dedicated an organ by Hugo Spilker, the local tuner of the day. His instruments were largely amalgamations of used components. In a couple of decades, this one had become troublesome, with repair efforts becoming frequent and increasingly futile. One day in 1990, the organ technicians Huestis & Associates refused to waste their time and the parish's money on it further.