In 1736 Governor of Ceylon, Gustaaf Willem van Imhoff, sought approval from the Dutch East India Company to demolish the existing church within the Colombo Fort and construct a new one on the same site. However, the VOC refused this request, and it wasn’t until the arrival of Governor Julius Valentyn Stein van Gollenesse in 1743 that the impasse was overcome. He decided that the new church would be erected in the area beyond the city walls, which at the time was swamp and marshland. The Europeans mistook the packs of roaming jackals for wolves, and the area became known as Wolvendaal. The site that was selected was on a hill which commanded views across the town and over the harbour and was in proximity to the town’s entrance. The site was also occupied by a small church, which had existed from the earliest period of Dutch occupation, when the Wolvendaal neighbourhood was a quiet suburban parish.
The foundations of the church were laid in 1749 and it took eight years to build. It was completed on 6 March 1757, when it was dedicated for public worship by Rev. Matthias Wirmelskircher, Rector of the Colombo Seminary. At the dedication there were two Governors present, Joan Gideon Loten and his successor Jan Schreuder, together with Members of the Council, Reverend Ministers (Predikants), prominent Burghers and their families.