The church was built under the stewardship of the Methodist Christian, the Reverend Charles Walker Posnett, who was driven by the motto My best for my Lord. Charles Posnett had arrived in Secunderabad in 1895, and after first ministering among British soldiers at Trimullghery, had launched into the villages and had reached Medak village in 1896. In those days there was no railway to Medak (the journey of 60 miles (97 km) from Hyderabad had to be done on horseback - and Posnett could do it in a day) and in the whole Medak area there were hardly two hundred Christians, who were using a small tiled house as their place of worship. As the number of Christians increased, Charles Posnett raised a moderate structure in the Mission Compound in the shape of a church, but thought it unworthy, and early in 1914 laid the foundations of the present cathedral church, on 1,000 acres (4.0 km2) of land in Ghusnabad area. When the people of Medak district were suffering from famine between 1919 and 1921, Charles Posnett helped them by employing them in the construction of the church instead of running a free kitchen. Construction went on for 10 years. Charles Posnett consecrated the church in 1924, thanking God for mitigating the sufferings of the people. When several Christian groups became re-united as the Church of South India, the church became the cathedral church of the diocese of Medak in October 1947.
The cathedral is 100 ft (30 m) wide and 200 ft (61 m) long, and conforms to the Gothic Revival style. It can accommodate about 5,000 people at a time. The mosaic tiles were imported from Britain and are of six different colours. Italian masons from Bombay were engaged for laying the decorative flooring. Massive pillars built with fine-hewn and well dressed grey stone support the gallery and the whole edifice. The roof of the church is made sound-proof by means of hollow sponge material, and has an impressive style of vaulting. The surface of the vaulting has the shape of squares. The bell-tower is 175 ft (53 m) high. (It is said that when the nizam of Hyderabad discovered that the church would be higher than the Charminar, he made a vain bid to have its height reduced.