On 5 May 1845, a committee comprising Reverend Hermann Randall von Dadelszen, Colonel James Campbell, Colonel William Henry Slade (Royal Engineers), Captain Nelson (Royal Engineers), Lieutenant Albert Watson (Ceylon Rifle Regiment), E. R. Power (Ceylon Civil Service), H. C. Selby, C. Temple and E. F. Gepp met to discuss the construction of a church in Nuwara Eliya, at an estimated cost of £900.[1] Captain Nelson designed the building with the construction work done chiefly by the officers and men of the local garrison of the 15th Regiment, under the supervision of Major James Brunker.[1]
It took seven years after building commenced for the church to be completed. Upon its completion it was consecrated by BishopJames Chapman on 24 February 1852 (St. Matthias’ Day).[1][2] The first vicar of the Holy Trinity Church, from 1843 to 1846, was Rev. von Dadelszen.
In the late 1890s the congregation proposed enlarging the Church, there was however some opposition, who proposed the construction of a new Church near the old cemetery.[1] The majority of the congregation however preferred the existing site. In 1889 the church was enlarged. The original portion of the building is at the church's western end. The additions can be noted by the difference in size of the corbels supporting the main rafters.[1]
The churchyard also several tombstones, including ones for Lady Olive Mary Caldecott, wife of Sir Andrew Caldecott, the penultimate Governor of Ceylon, and the family members of Sir Samuel Baker.