Anglican Chinese services in Singapore could possibly trace their origin to 1856, when a stirring Whitsunday sermon by Revd William Humphrey of St Andrew's Church (now St Andrew's Cathedral) aroused interest in setting up local congregations. St Andrew's Church Mission was later established and grew in strength following the arrival of Revd William Henry Gomes (1827-1902), a missionary who had served in Sarawak and who spoke Tamil, Malay and Dyak, in 1872. Revd Gomes later learnt Hokkien in Singapore.
Foochow-speaking mission work began in 1902 under the leadership of Revd R. Richard. In 1910, Revd Dong Bin Seng (1871-1961) was engaged from Foochow, China, to work with the Foochow congregation in Singapore. In 1927, Revd Ng Ho Le arrived from Penang to serve the local Hokkien-speaking community. Services in the Foochow and Hokkien dialects were held at St Peter's Church in the compound of St Andrew's School at Stamford Road until it was acquired by the government in 1937 for the building of the former National Library (which was in turn torn down in 2005) and hence resulted in the shift to its present site. The Foochow Parish and the Hokkien Parish eventually formed the Holy Trinity Parish in 1984.
Built with Chinese-style green tiled roofs and decorative elements, the church was designed by Ho Kwong Yew in a vernacular Art Deco style intended to make it easier for locals to relate to the buidling. Unlike most churches, the altar and nave (where the services are held) were located on the second level. The ground floor housed an assembly area with a stage, which served as a kindergarten from 1953 until the 1970s. A new five-storey Annex Building behind the original hall was completed and dedicated by the Most Rev. Dr John Chew, Bishop of the Anglican Diocese of Singapore, on 24 July 2011 during the Church's 70th Anniversary Service.